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.

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ę f P, która dla wejścia n wynosi 1, jeśli P zatrzymuje się po n krokach lub mniej. Pierwszym przecięciem f P i stałą funkcją 1 jest czas działania P , jeśli$P$$f_P$$n$$1$$P$$n$$f_P$$1$$P$$P$$f_P$$1$

$T$$T$