Algorytm politime i polyspace do wyznaczania wiodącego przecięcia n dyskretnych funkcji monotonicznych

Some frontmatter: Jestem informatykiem rekreacyjnym i zatrudnionym inżynierem oprogramowania. Więc przepraszam, jeśli to podpowiedź wydaje się być trochę poza lewym polem - rutynowo gram z matematycznymi symulacjami i otwieram problemy, gdy nie mam nic lepszego do roboty.

Podczas zabawy hipotezą Riemanna ustaliłem, że pierwszą lukę można zredukować do relacji powtarzalności opartej na przecięciu wszystkich funkcji uzupełniających utworzonych przez wielokrotności każdej poprzedniej liczby pierwszej (uważni obserwatorzy zauważą, że jest to uogólnienie sito Eratostenesa ). Jeśli nie ma to dla ciebie żadnego sensu, nie martw się - nadal jest to problem. $n-1$

Widząc, jak te funkcje są powiązane, zdałem sobie sprawę, że następne wystąpienie każdej liczby pierwszej można sprowadzić do pierwszego przecięcia tych funkcji, powtarzając się w nieskończoność. Nie udało mi się jednak ustalić, czy jest to możliwe w przypadku politytime i polyspace. Tak więc: szukam algorytmu, który może określić pierwsze przecięcie dyskretnych (i, jeśli to możliwe, monotonicznych) w wielomianowym czasie i przestrzeni. Jeśli taki algorytm obecnie nie istnieje lub nie może istnieć, wystarczy krótki zwięzły dowód lub odniesienie. $n$

Jak dotąd mogę znaleźć algorytm projekcji Dykstry (tak, to RL Dykstra, a nie Edsger Dijkstra ), który moim zdaniem sprowadza się do problemu programowania liczb całkowitych i dlatego jest trudny do NP. Podobnie, jeśli wykonamy przecięcie zbioru przechodniego wszystkich odpowiednich punktów (ponieważ są one obecnie rozumiane jako ograniczone), nadal musimy ograniczyć się do wykładniczej przestrzeni dla naszego ponownego wystąpienia z powodu obecnej słabej granicy liczby pierwsze dla dowolnego rzeczywistego (a zatem przestrzeni dla każdej liczby pierwszej ). $\ln(m)$ $m$ $e^n$ $n$

Globalnie zastanawiam się, czy moje rozumienie ograniczenia problemu jest błędne. Nie spodziewam się, że w najbliższym czasie rozwiążę hipotezę Riemanna (lub jakikolwiek głęboki, otwarty problem w tej przestrzeni). Staram się raczej dowiedzieć o tym więcej, bawiąc się tym problemem, i wpadłem na kłopoty w swoich badaniach.

algorithms reference-request discrete-mathematics

— MrGomez
źródło

Przez przecięcie dwóch funkcji i , powiedzmy, masz na myśli wartości

f

$f$

g

$g$

n

$n$ takie

f (n) = g (n)

$f(n)=g(n)$

— Dave Clarke

@DaveClarke Correct. Przepraszam za zwięzłość i niedokładne określenie problemu; Przyznaję otwarcie, że to pytanie można ulepszyć teraz, gdy w mojej głowie ramka pytań jest nieco jaśniejsza.

— MrGomez

@MrGomez, są to arbitralne funkcje monotoniczne, czy może istnieje na nich inne ograniczenie?

— user834

@ user834 Ponowne odczytanie mojego pierwotnego zamiaru za pomocą tego postu miało na celu zbadanie wiodącego przecięcia zbioru funkcji związanych jedną zmienną (na przykład:

). Od tego czasu streściłem równanie w kategoriach ciągłych funkcji trygonometrycznych zamiast monotonicznych, aby sprawdzić, czy dla kompozycji może istnieć solver wieloprzestrzenny i kosmiczny. Do tej pory nie miałem szczęścia, ale w ostatnich tygodniach nie miałem okazji na to spojrzeć.

m i n (n > 2 ∣ 2 n + 1 \cap 3 n + 1 \cap 3 n + 2)

$min(n > 2 \mid 2n+1 \cap 3n+1 \cap 3n+2)$

— MrGomez

Dykstra i Dijkstra to ta sama nazwa. „y” jest ligaturą dla „ij”, która jest „literą” w holenderskim alfabecie: en.wikipedia.org/wiki/IJ_(digraph) .

— Yuval Filmus

Ustalenie, czy dwie funkcje monotoniczne podane jako programy przecinają się, nie jest obliczalne. Podobnie, określenie pierwszego skrzyżowania w ramach obietnicy, że ono istnieje, jest „arbitralnie trudne” (zdecydowanie nie polytime).

Dla danego programu zdefiniuj funkcję która dla wejścia wynosi jeśli zatrzymuje się po krokach lub mniej. Pierwszym przecięciem i stałą funkcją jest czas działania , jeśli $P$ $f_P$ $n$ $1$ $P$ $n$ $f_P$ $1$ $P$ $P$ $f_P$ $1$

$T$ $T$

— Yuval Filmus
źródło

Naprawdę podoba mi się ta odpowiedź. Jest zwięzły, wystarczająco ogólny, aby objąć zakres mojego pytania, i odnosi mój problem do aspektu, którego nie wziąłem pod uwagę: trudność problemu zatrzymania. To da sobie radę. Dziękuję Ci!

— MrGomez