Jaki jest najstarszy otwarty problem w TCS?

36

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.

Robin Kothari
źródło
13
„Jaki jest najlepszy sposób przyrządzania mięsa?” Jaki jest najlepszy algorytm do przygotowywania posiłków w modelu obliczeniowym przy ognisku? - istotne tysiące lat temu, wciąż aktualne! Plus jest dużo literatury na ten temat! (Przepraszam, nie mogłem się oprzeć ;-))
Daniel Apon
3
Czy jest jakiś bóg? Może to być problem TCS, jeśli można go rozwiązać za pomocą komputerów.
Sariel Har-Peled
9
@Daniel, „jaki jest najlepszy sposób na pokrojenie ciasta” to aktualne pytanie TCS !!!
Suresh Venkat
3
#offtopic: Miło widzieć, że supercooldave ma teraz nazwę :)
Suresh Venkat
5
Znalazłem książkę zatytułowaną „Historia algorytmów: od kamyka do mikroczipa” ( amazon.com/dp/3540633693 ). Może to być pomocne w znalezieniu porządnej historii (nowych i starych) algorytmów.
MS Dousti

Odpowiedzi:

38

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ń.

Jeffε
źródło
9
W przeciwieństwie do Robina nie sądzę, aby uzasadnione było naleganie na postawienie pytania w jego nowoczesnej formie. To jak trzymanie dowodów historycznych według współczesnych standardów rygorystyczności. Zgodnie z tym standardem geometria aksjomatyczna zaczęła się od Kleina, a Euclid był tylko machającym ręką greckim kolesiem.
Jeffε,
6
„Według współczesnych standardów rygorystycznych, Euclid był po prostu ręcznym greckim kolesiem”: to mój następny .sig :)
Suresh Venkat
2
Myślę, że takie przykłady są w porządku. To, czego chciałem uniknąć, to to, co wydarzyło się przy przepełnieniu matematyki: istniał spór o to, czy Grecy rozważali jakiś problem tylko dlatego, że studiowali jakiś powiązany problem. Inną rzeczą, której chcę uniknąć, są pytania filozoficzne, takie jak „Czy wszechświat deterministyczny” przekształcony w problem P w porównaniu z BPP. Podałeś konkretny problem, który został uznany przez ludzi, którzy go przedstawili, za problem obliczeniowy, i jest to całkowicie do przyjęcia.
Robin Kothari,
To pytanie zostało częściowo rozwiązane w przypadku mnożenia liczb całkowitych online. arxiv.org/abs/1101.0768
felix
23

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”.

arnab
źródło
2
Bardzo fajny cytat. To wspaniale, że Gauss jasno stwierdził, że obecne algorytmy faktoringu były „pracochłonne i ciągłe”!
Robin Kothari,
10

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):

(qN)=1(qN)

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?

MS Dousti
źródło
9

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:

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

MS Dousti
źródło
1
Ponieważ ograniczam to do rygorystycznych sformułowań problemów, zgaduję, że kwestię faktoringu i FP = FNP można sformalizować dopiero wtedy, gdy będziemy mieli maszyny Turinga i czas wielomianowy itp.
Robin Kothari
@Robin: Nie możesz prosić o stare, sformalizowane problemy z otwartym TCS, jeśli nie było nawet komputerów w starszym wieku! :)
MS Dousti
1
@Sadeq: Nie mam nic przeciwko, jeśli najstarsze pytanie okaże się pytaniem zadanym w 1922 r. Nalegam na rygorystyczne pytania, ponieważ w przeciwnym razie ludzie będą cytować 4000-letnie teksty, twierdząc, że jakieś zdanie o wszechświecie było pytaniem obliczeniowym w przebraniu.
Robin Kothari,
W którym roku sformułowano ten problem?
Dave Clarke
3
@Sadeq: Prawda, ale to nie jest pytanie P kontra NP, chyba że ktoś sformalizuje model itp. Mam na myśli, że równie dobrze może reprezentować jakieś inne pytanie (powiedzmy L kontra NL, P / poli kontra NP / poli lub jakieś pytanie w inne pole). Po drugie, jest to powszechne przekonanie, a nie coś, co uważa się za otwarty problem. Nie jest to coś, co wymaga dowodu, w swoim oryginalnym sformułowaniu: to tylko obserwacja życia.
Robin Kothari,
3

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?

TMxTMy

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.

vzn
źródło
7
nie zgadzam się z większością tego, co mówisz (fakt, że możesz konstruować wszelkiego rodzaju maszyny Turinga, które zatrzymują się, jeśli istnieją jakieś domniemane obiekty, nie sprawia, że ​​problemy z ich istnieniem są trudne do obliczenia). ale na koniec masz rację: deterministyczne generowanie liczby pierwszej w pewnym zakresie jest rozsądną nowoczesną wersją starego poszukiwania „formuły na liczby pierwsze”. chciałbym głosować, jeśli napiszesz skoncentrowaną odpowiedź w tym duchu
Sasho Nikolov
1
Zgadzam się z powyższym komentarzem: hipotezę Poincare można sformułować jako problem zatrzymania również dla maszyn Turinga, ale nie osiągnięto żadnego postępu przy użyciu technik specjalnie ze strony społeczności CS. To samo można powiedzieć o wielu problemach teoretycznych, które mogą być istotne obliczeniowo.
cody
2

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

Sariel Har-Peled
źródło
0

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?

T2(n)T(n)logT(n)

logT(n)

chazisop
źródło
1
logT(n)
1
PNP
1
Można by to wyjaśnić, z korzyścią dla tych, którzy nie znają szczegółowo tych dokumentów: Jaki rodzaj TM jest symulowany? Jaki typ maszyny wykonuje symulację?
funkstar
Nie uważam, że konieczne jest wyjaśnienie. Fakt, że modelem zastosowanym w pierwszym artykule jest multitape TM, jest dobrze znanym faktem, ponieważ zawiera niektóre podstawowe definicje TCS, a ponadto jest wyraźnie wymieniony w tytule artykułu Hennie and Stearns.
chazisop
1
Moim zdaniem sformułowanie otwartego pytania jest nadal zbyt niejasne. Mimo, że jest dobrze znany w społeczności ToC że Hartmanis, Hennie i praca Stearns z multitape bazach, że tylko sprawia odpowiedź nieprzydatny do tych w wielu innych dziedzinach TCS. Rozważ przynajmniej dodanie do pytania kwalifikatora „multitape”. (I nawet wtedy masz problem z tym, że symulacja Hartmanisa i Stearnsa używa 1 taśmy TM, podczas gdy symulacja Hennie i Stearnsa używa 2 taśmy TM.)
funkstar