Jaki jest najstarszy otwarty problem w TCS?

Ten problem jest inspirowany pytaniem MO , które moim zdaniem było bardzo interesujące.

Jaki jest najstarszy otwarty problem w TCS?

To pytanie wymaga wyjaśnienia.

Po pierwsze, czym jest TCS? Myślę, że istnienie liczb nieparzystych idealnych nie jest TCS. Powiedziałbym, że dziesiątym problemem Hilberta jest TCS. Myślę, że problemy takie jak „Czy możemy zbudować X za pomocą linijki i kompasu” to także TCS, ponieważ proszą o algorytm w ograniczonym modelu obliczeniowym. Może nie być ścisłego sposobu zdefiniowania problemu TCS, ale skorzystaj z własnego osądu. Być może jednym z testów jest „Jeśli problem zostanie rozwiązany, czy najprawdopodobniej pojawiłby się w STOC / FOCS? Czy badaczem, który go rozwiązał, byłby prawdopodobnie informatyk teoretyczny?”

Po drugie, czym jest „najstarszy”? Mam na myśli najstarszy według daty. Podana data powinna być również możliwa do zweryfikowania, ale nie sądzę, że powinna być zbyt trudna.

Po trzecie, czym jest „otwarty problem”? Przez „problem otwarty” rozumiem problem, który w pewnym momencie był uważany za otwarty. Być może pojawił się na końcu artykułu w sekcji otwartych problemów, a może istnieją dowody na to, że niektórzy pracowali nad nim i ponieśli porażkę, a może w literaturze istnieją niepoprawne dowody, które sugerują, że został on zbadany. Przykład czegoś, co nie spełnia tych kryteriów: „Grecy badali obiekty X i Y. Z jest wyraźnie obiektem pośrednim, na pewno zastanawiali się, czy można go zbudować”. Jeśli nie ma literatury na temat Z z tego okresu, to nie jest to otwarty problem z tego okresu.

Po czwarte, co mam na myśli przez „problem”? Mam na myśli konkretne pytanie „tak / nie”, a nie coś w rodzaju „Scharakteryzuj wszystkie obiekty X za pomocą właściwości Y”, ponieważ na takie pytania często nie ma zadowalającej odpowiedzi. Często zdarza się brak porozumienia co do tego, czy pytanie zostało rozwiązane. Nie wchodźmy tutaj w takie pytania. Jeśli nie jest to pytanie tak / nie, ale jasne jest, że jest naprawdę otwarte, to też jest w porządku. (W przypadku, gdy nie jest to jasne, przez „problem” mam na myśli sformułowany problem. Proszę nie przekształcać jakiejś ludowej legendy o hazardzie w XVI wieku na pytanie o BPP i PSPACE.)

Wreszcie, ponieważ nie jest to pytanie z dużej listy, proszę opublikować odpowiedź tylko wtedy, gdy uważasz, że jest starsza niż odpowiedzi już opublikowane (lub jeśli uważasz, że opublikowane odpowiedzi nie spełniają innych warunków - na przykład, że nie są TCS, lub nie są otwarte). To nie jest masowa kolekcja starych otwartych problemów.

Jaka jest złożoność obliczeniowa mnożenia liczb całkowitych? Prawdopodobnie pytanie to sięga przynajmniej algorytmu „duplikacji i mediacji” dla mnożenia liczb całkowitych opisanego w Rhind Mathematical Papyrus, który został napisany około 1650 rpne , ale twierdzi, że jest kopią znacznie starszego dokumentu.

Trzeba przyznać, że papirus Rhinda nie wziął pod uwagę złożoności algorytmu. Więc może lepszym rozwiązaniem jest złożoność rozwiązywania układów równań liniowych? Badania nad wydajnymi algorytmami rozwiązywania układów liniowych sięgają przynajmniej komentarza Liu Hui, opublikowanego w 263 r. , Na temat Dziewięciu rozdziałów o sztuce matematycznej . W szczególności Liu Hui porównuje dwa warianty tego, co jest obecnie uznawane za eliminację Gaussa, i zlicza liczbę operacji arytmetycznych używanych przez każdą z nich, z wyraźnym celem znalezienia bardziej wydajnej metody.

Oba te pytania są nadal przedmiotem aktywnych badań.

Poszukiwanie wydajnego algorytmu faktoringu sięga przynajmniej Gaussa. Artykuł 329 Gaussa Disquitiones Arithmeticae (1801) zawierał następujący cytat ( źródło ):

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length. ... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.

Oczywiście to prawda, że ​​Gauss formalnie nie zdefiniował dokładnie tego, czego chciał z algorytmu faktoringu. W tym samym artykule mówił jednak o tym, że wszystkie znane wówczas algorytmy testowania pierwotności były bardzo „pracochłonne i ciągłe”.

Poniżej cytowane z

• Goldwasser, S. i Micali, S. 1982. Probabilistyczne szyfrowanie i jak grać w mentalnego pokera, zachowując w tajemnicy wszystkie częściowe informacje. W postępowaniu z czternastego dorocznego sympozjum ACM na temat teorii obliczeń (San Francisco, Kalifornia, Stany Zjednoczone, 05 - 07 maja 1982 r.). STOC '82. ACM, Nowy Jork, Nowy Jork, 365-377. DOI = http://doi.acm.org/10.1145/800070.802212

Odnosi się do innego problemu z czasów Gaussa Disquitiones Arithmeticae (1801):

$(\frac{q}{N})=1$$(\frac{q}{N})$

PS: Do tej pory znamy dwa z czterech problemów algorytmicznych :

1. Faktoring (jak wspomniano w arnab);
2. Decydująca kwadratowa rezydencja.

jakie są pozostałe dwa problemy opisane przez Gaussa?

W literaturze naszego kraju jest powiedzenie, które dosłownie tłumaczę jako „Zagadka staje się łatwa, gdy zostanie rozwiązana”. Choć nie jest to dobre tłumaczenie, odnosi się do faktu, że mając rozwiązanie, możesz je łatwo zweryfikować; jeszcze wcześniej zagadka wydaje się bardzo trudna.

Odnosi się to do znanego obecnie problemu „FP vs. FNP”: jeśli FNP = FP, weryfikacja odpowiedzi na zagadkę jest tak łatwa, jak jej znalezienie. Jednak jeśli FNP ≠ FP, istnieją „zagadki”, dla których znalezienie rozwiązania jest znacznie trudniejsze niż weryfikacja rozwiązania.

Wierzę, że ten problem jest najstarszym otwartym problemem TCS, ale jego rygorystyczne sformułowanie sięga około 30 lat temu!

There seems to be a similar (yet somehow different!) proverb in the English language: "It's easy to be wise after the event" or "It's easy to be smart after the fact."

EDYCJA: „Czy możemy uwzględnić liczby w czasie wielościennym” to kolejny otwarty problem TCS, ale myślę, że jest on młodszy niż wspomniany powyżej problem.

Oto dwie listy otwartych problemów TCS w Internecie:

• http://www.c2.com/cgi/wiki?OpenProblemsInComputerScience
• http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science

Mamy również taką listę tutaj na CSTheory.

Kwestionuję twoją wykluczającą teorię liczb obejmującą pytania, czy niektóre zestawy teorii liczb są skończone czy nieskończone jako część TCS i zdecydowanie twierdziłbym inaczej. Grecy pytali, czy:

• czy są jakieś nieparzyste liczby idealne? [prawdopodobnie rozważany przez euclida]

• czy istnieje nieskończona liczba podwójnych liczb pierwszych?

$TM_x$$TM_y$

więc zapewne są to dwa starożytne problemy algorytmiczne, a Grecy pionierzy najwcześniejszych TCS głównie w postaci teorii liczb, a problemy z wczesną teorią liczb są tylko szczególnymi przypadkami zatrzymania problemu przez Turingsa i wczesnymi poszlakami na jego trudność. istnieje ścisły związek między pytaniem o / znalezieniem / poszukiwaniem dowodów a teorią nierozstrzygalności.

prawdopodobnie nowe badania pokazują hipotezę Collatza, która kiedyś uważana była za ciekawość teorii liczb, ma głębokie powiązania z teorią obliczalności i może leżeć na granicy między nierozstrzygalnymi i rozstrzygalnymi problemami. także przykład, który zacytowałeś w 10. problemie Hilberta pokazuje bardzo fundamentalny związek między teorią liczb a TCS.

dwa inne starożytne pytania algorytmiczne:

• jaki jest wydajny lub najbardziej wydajny algorytm obliczania gcd, największego wspólnego dzielnika?

• jaki jest wydajny lub najbardziej wydajny algorytm obliczania liczb pierwszych?

zgodził się, że drugie pytanie jest dość ściśle związane z faktoringiem, ale oczywiście nie jest takie samo. rozważano to przez sito i euklides Eratostenesa. oczywiście ostatnio wykazano, że jest w P przez AKS, ale nawet wtedy algorytm nie jest całkowicie optymalny.

istnieją bardzo nowoczesne badania TCS nad algorytmem gcd euklidów (tj. XX wiek), które wykazały, że liczby Fibonacciego dają mu najgorszą wydajność. [nie jestem pewien, kto pierwszy to pokazał]

dopóki algorytm euclidów nie zostanie uznany za optymalny, prawdopodobnie wydajne obliczenia gcd są nadal otwarte.

Nie jestem pewien, jak poważna jest ta odpowiedź, ale ...

To naprawdę zależy od tego, jak szeroko chcesz zdefiniować swoje pytanie.

Z pewnością „czy można zbudować inteligentną maszynę?” jest najstarszym otwartym pytaniem w CS, które zapoczątkowało informatykę, ale prawdopodobnie jest starsze o milinium lub dwa niż CS. Nie? (To pytanie teoretyczne, ponieważ wymaga odpowiedzi - nie samej maszyny ...)

Naturalnym odniesieniem do poszukiwania inteligentnej maszyny byłby Golem ... http://en.wikipedia.org/wiki/Golem#History

Mogę odpowiedzieć na twoje pytanie ze 100% pewnością przez pewien czas. Jeśli weźmiemy pod uwagę okres od przełomowego artykułu Hartmanisa i Stearnsa do dowolnego punktu w przyszłości, najstarszym problemem w TCS, który jest nadal otwarty, jest:

Jakie jest minimalne obciążenie potrzebne do symulacji deterministycznych baz TM?

$T^{2}(n)$$T(n)$$\log T(n)$

$\log T(n)$