Was ist das älteste offene Problem in TCS?

36

Dieses Problem ist von dieser MO-Frage inspiriert , die ich sehr interessant fand.

Was ist das älteste offene Problem in TCS?

Diese Frage muss eindeutig geklärt werden.

Was ist TCS? Ich denke, die Existenz von ungeraden perfekten Zahlen ist nicht TCS. Ich würde sagen, dass Hilberts zehntes Problem TCS ist. Ich denke, Probleme wie "Können wir X mit einem Lineal und einem Kompass konstruieren" sind auch TCS, da sie nach einem Algorithmus in einem eingeschränkten Rechenmodell fragen. Es gibt möglicherweise keine strenge Methode, um zu definieren, was ein TCS-Problem ist, aber Sie können Ihr Urteilsvermögen verwenden. Vielleicht lautet ein Test: "Wenn dies gelöst wird, würde es höchstwahrscheinlich in STOC / FOCS erscheinen? Wäre der Forscher, der es gelöst hat, höchstwahrscheinlich ein theoretischer Informatiker?"

Zweitens, was ist "am ältesten"? Ich meine am ältesten nach Datum. Das angegebene Datum sollte auch überprüfbar sein, aber ich denke nicht, dass dies zu schwer sein sollte.

Drittens, was ist ein "offenes Problem"? Mit "offenes Problem" meine ich ein Problem, das zu einem bestimmten Zeitpunkt als offen angesehen wurde. Vielleicht ist es am Ende eines Artikels im Abschnitt über offene Probleme erschienen, oder vielleicht gibt es Hinweise darauf, dass einige Leute daran gearbeitet haben und fehlgeschlagen sind, oder vielleicht gibt es falsche Beweise in der Literatur, die darauf hindeuten, dass es untersucht wurde. Ein Beispiel für etwas, das nicht diesen Kriterien entspricht: "Die Griechen haben die Objekte X und Y untersucht. Z ist eindeutig ein Zwischenobjekt, sie haben sich sicherlich gefragt, ob es konstruiert werden kann." Wenn es keine Literatur zu Z aus dieser Zeit gibt, ist es kein offenes Problem aus dieser Zeit.

Viertens, was meine ich mit "Problem"? Ich meine eine bestimmte "Ja / Nein" -Frage und nicht so etwas wie "Charakterisiere alle Objekte X mit der Eigenschaft Y", weil solche Fragen oft keine zufriedenstellende Antwort haben. Sehr oft wird es Meinungsverschiedenheiten darüber geben, ob die Frage gelöst wurde. Lassen Sie uns hier nicht auf solche Fragen eingehen. Wenn es keine Ja / Nein-Frage ist, aber klar ist, dass es wirklich offen ist, ist das auch in Ordnung. (Falls dies nicht klar ist, meine ich mit "Problem" ein formal festgelegtes Problem. Bitte konvertieren Sie keine Volkslegende über das Glücksspiel im 16. Jahrhundert in eine Frage zu BPP und PSPACE.)

Da es sich bei dieser Frage nicht um eine große Liste handelt, senden Sie eine Antwort nur, wenn Sie der Meinung sind, dass sie älter als die bereits veröffentlichten Antworten ist (oder wenn Sie der Meinung sind, dass die veröffentlichten Antworten eine andere Bedingung nicht erfüllen - als wären sie keine TCS, oder sie sind nicht offen). Dies ist keine wahllose Sammlung alter offener Probleme.

Robin Kothari
quelle
13
"Was ist der beste Weg, um Fleisch zu kochen?" Welcher Algorithmus eignet sich am besten für die Zubereitung von Speisen nach einem Modell der Lagerfeuerberechnung? - relevant vor vielen tausend jahren, heute noch relevant! Außerdem gibt es eine Menge Literatur zu diesem Problem! (Entschuldigung, ich konnte nicht widerstehen ;-))
Daniel Apon
3
Gibt es einen Gott? Könnte ein TCS-Problem sein, wenn es von Computern gelöst werden kann.
Sariel Har-Peled
9
@ Daniel, "Was ist der beste Weg, um einen Kuchen zu schneiden", ist eine aktuelle TCS-Frage !!!
Suresh Venkat
3
#offtopic: Schön zu sehen, dass Supercooldave jetzt einen Namen hat :)
Suresh Venkat
5
Ich fand ein Buch mit dem Titel "Eine Geschichte der Algorithmen: Vom Kiesel zum Mikrochip" ( amazon.com/dp/3540633693 ). Dies kann hilfreich sein, um eine anständige Historie für (neue und alte) Algorithmen zu finden.
MS Dousti

Antworten:

38

Was ist die rechnerische Komplexität der ganzzahligen Multiplikation? Diese Frage geht vermutlich zumindest auf den Algorithmus zur Vervielfältigung und Vermittlung von Ganzzahlen zurück, der im Rhind Mathematical Papyrus beschrieben ist, der um 1650 v. Chr . Verfasst wurde.

Zugegeben, der Rhind-Papyrus hat die Komplexität dieses Algorithmus nicht explizit berücksichtigt. Vielleicht ist eine bessere Antwort: Wie komplex ist das Lösen linearer Gleichungssysteme? Forschung in effiziente Algorithmen zur Lösung linearer Gleichungssysteme Daten zumindest Liu Hui Kommentar zurück, die in der veröffentlichten 263 AD , auf Jiu Zhang Suanshu . Im Einzelnen vergleicht Liu Hui zwei Varianten der heute als Gauß'schen Eliminierung bekannten Methode und zählt die Anzahl der von jeder verwendeten Rechenoperationen mit dem ausdrücklichen Ziel, die effizientere Methode zu finden.

Beide Fragen sind nach wie vor Gegenstand aktiver Forschung.

Jeffε
quelle
9
Im Gegensatz zu Robin halte ich es nicht für vernünftig, darauf zu bestehen, dass die Frage in ihrer modernen Form gestellt wurde. Das ist so, als würde man historische Beweise für zeitgenössische Standards der Strenge aufbewahren. Nach diesem Standard begann die axiomatische Geometrie mit Klein, und Euklid war nur ein griechischer Typ, der von Hand winkte.
Jeffs
6
"Nach modernen Maßstäben der Strenge war Euklid nur ein griechischer Typ mit der Hand": Das ist mein nächster .sig :)
Suresh Venkat
2
Ich denke, solche Beispiele sind in Ordnung. Was ich vermeiden wollte, ist das, was beim mathematischen Überlauf passiert ist: Es gab einen Streit darüber, ob die Griechen ein Problem in Betracht zogen, nur weil sie ein verwandtes Problem untersucht hatten. Das andere, was ich vermeiden möchte, sind philosophische Fragen wie "Ist das Universum deterministisch", die in das Problem P versus BPP umgewandelt werden. Sie haben ein bestimmtes Problem angegeben, das von den Personen, die es gestellt haben, als Rechenproblem angesehen wurde, und das ist vollkommen akzeptabel.
Robin Kothari
Diese Frage wurde für die Online-Ganzzahlmultiplikation teilweise gelöst. arxiv.org/abs/1101.0768
felix
23

Die Suche nach einem effizienten Algorithmus für das Factoring geht anscheinend auf mindestens Gauß zurück. Artikel 329 von Gauss ' Disquitiones Arithmeticae (1801) hatte das folgende Zitat ( Quelle ):

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.

Natürlich ist es richtig, dass Gauß formal nicht genau definiert hat, was er sich vom Factoring-Algorithmus gewünscht hat. In demselben Artikel sprach er jedoch darüber, dass alle damals bekannten Primalitätstest-Algorithmen sehr "mühsam und prolix" waren.

Arnab
quelle
2
Sehr schönes Zitat. Es ist großartig, wie Gauß klar war, dass die aktuellen Factoring-Algorithmen "mühsam und prolix" waren!
Robin Kothari
10

Das Folgende, zitiert aus

  • Goldwasser, S. und Micali, S. 1982. Probabilistische Verschlüsselung & wie man mentales Poker spielt, wobei alle Teilinformationen geheim bleiben. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing (San Francisco, Kalifornien, USA, 5.-07. Mai 1982). STOC '82. ACM, New York, NY, 365-377. DOI = http://doi.acm.org/10.1145/800070.802212

Bezieht sich auf ein anderes Problem, das auf Gauss 'Disquitiones Arithmeticae (1801) zurückgeht:

(qN)=1(qN)

PS: Inzwischen kennen wir zwei der vier algorithmischen Probleme :

  1. Factoring (wie von Arnab erwähnt);
  2. Quadratische Residuen bestimmen.

Was sind die beiden verbleibenden Probleme, die Gauß beschreibt?

MS Dousti
quelle
9

In der Literatur unseres Landes gibt es ein Sprichwort, das ich wörtlich als "Das Rätsel wird leicht, wenn es gelöst ist." Obwohl keine gute Übersetzung, bezieht sie sich auf die Tatsache, dass Sie die Lösung leicht überprüfen können, wenn Sie sie haben. Davor scheint das Rätsel sehr schwer zu sein.

Dies bezieht sich auf das mittlerweile bekannte "FP vs. FNP" -Problem: Wenn FNP = FP, ist die Überprüfung der Antwort auf das Rätsel so einfach wie das Auffinden. Wenn jedoch FNP ≠ FP ist, gibt es "Rätsel", für die das Finden einer Lösung viel schwieriger ist als das Überprüfen der Lösung.

Ich glaube, dieses Problem ist das älteste offene TCS-Problem, doch seine strenge Formulierung reicht bis vor knapp 30 Jahren zurück!

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

EDIT: "Können wir Zahlen in Poly-Zeit faktorisieren" ist ein weiteres offenes TCS-Problem, aber ich denke, es ist jünger als das oben erwähnte Problem.

Hier ist eine Liste von zwei offenen TCS-Problemen im Web:

Wir haben auch eine solche Liste hier auf CSTheory.

MS Dousti
quelle
1
Da ich es auf rigorose Formulierungen von Problemen beschränke, würde ich vermuten, dass die Frage des Factorings und FP = FNP nur formalisiert werden kann, wenn wir Turing-Maschinen, Polynomzeit usw. haben.
Robin Kothari
@Robin: Du darfst nicht nach alten, formalisierten TCS-Open-Problemen fragen, wenn es im Alter nicht einmal Computer gäbe! :)
MS Dousti
1
@Sadeq: Es macht mir nichts aus, wenn sich herausstellt, dass die älteste Frage 1922 gestellt wurde. Ich bestehe auf rigoros formulierten Fragen, da die Leute sonst 4000 Jahre alte Texte zitieren, in denen behauptet wird, ein Satz über das Universum sei eine Rechenfrage verkleidet.
Robin Kothari
In welchem ​​Jahr wurde dieses Problem formuliert?
Dave Clarke
3
@Sadeq: Stimmt, aber das ist nicht die Frage P gegen NP, es sei denn, jemand formalisiert das Modell usw. Ich meine, es könnte genauso gut eine andere Frage darstellen (z. B. L gegen NL oder P / Poly gegen NP / Poly oder eine Frage in ein anderes Feld). Zweitens ist dies eine weit verbreitete Überzeugung und kein offenes Problem. Es ist in seiner ursprünglichen Formulierung nicht beweispflichtig: Es ist nur eine Beobachtung des Lebens.
Robin Kothari
3

Ich stelle Ihre ausschließende Zahlentheorie in Frage, die die Frage beinhaltet, ob einige zahlentheoretische Mengen als Teil von TCS endlich oder unendlich sind und definitiv anders argumentieren würden. Die Griechen fragten, ob:

  • are there any odd perfect numbers? [possibly considered by euclid]

  • are there an infinite number of twin primes?

these can easily be rephrased as computability theory questions based on the strong correspondence between questions about specific TM halting and most number theory questions. in the 1st case build a TMx that searches for odd perfect numbers, counting upwards and halts if it finds one. in the 2nd case build a machine TMy that uses a large upper bound in a search of a twin prime found after a prior twin prime pair. does it halt?

so arguably these are two ancient algorithmic problems and the greeks pioneered the earliest TCS mainly in the form of number theory and early number theory problems are just special cases of Turings halting problem, and early circumstantial evidence for its difficulty. and there is a close relation between asking about/finding/searching for proofs and undecidability theory.

arguably new research is showing the collatz conjecture, once considered a number theory curiosity, has deep liinks to computability theory, & may lie right at the boundary between undecidable and decidable problems. also the example you cite of hilberts 10th problem shows a very fundamental link between number theory and TCS.

two other ancient algorithmic questions:

  • Was ist ein effizienter oder der effizienteste Algorithmus für die Berechnung des größten gemeinsamen Divisors GCD?

  • Was ist ein effizienter oder effizientester Algorithmus für die Berechnung von Primzahlen?

Ich stimmte zu, dass die zweite Frage ziemlich eng mit Factoring zusammenhängt, aber es ist natürlich nicht ganz dasselbe. es wurde von Eratosthenes 'Sieb und Euklid betrachtet. Natürlich wurde kürzlich von AKS gezeigt, dass es in P ist, aber selbst dann ist der Algorithmus nicht als vollständig optimal erwiesen.

Es gibt sehr moderne TCS-Forschungen zum Euklid-GCD-Algorithmus (dh des 20. Jahrhunderts), die gezeigt haben, dass Fibonacci-Zahlen die schlechteste Leistung erbringen. [nicht sicher, wer das zuerst gezeigt hat]

Bis sich der Euklid-Algorithmus als optimal erwiesen hat, ist die wohl effiziente Berechnung von GCD noch offen.

vzn
quelle
7
Ich bin mit den meisten Ihrer Aussagen nicht einverstanden (die Tatsache, dass Sie alle Arten von Turing-Maschinen konstruieren können, die anhalten, wenn einige mutmaßliche Objekte existieren, stellt diese Existenzprobleme nicht in Frage der Berechenbarkeit). Aber am Ende haben Sie einen guten Punkt: Die deterministische Erzeugung einer Primzahl in einem gewissen Bereich ist eine vernünftige moderne Version der alten Suche nach einer "Formel für Primzahlen". Ich würde mich freuen, wenn Sie eine gezielte Antwort in diese Richtung schreiben
Sasho Nikolov
1
Ich stimme der obigen Bemerkung zu: Die Poincare-Vermutung kann auch für Turing-Maschinen als Stillstandsproblem formuliert werden, aber mit Techniken, die speziell von der CS-Community entwickelt wurden, wurden keine Fortschritte erzielt. Dasselbe kann für solche zahlentheoretischen Probleme gesagt werden, die möglicherweise rechenrelevant sind.
Cody
2

Ich bin mir nicht sicher, wie ernst diese Antwort ist, aber ...

Es hängt wirklich davon ab, wie weit Sie bereit sind, Ihre Frage zu definieren.

Sicher "kann man eine intelligente Maschine bauen?" ist die älteste offene Frage in CS, mit der die Informatik begonnen hat, die aber wahrscheinlich ein oder zwei Jahrtausende älter ist als CS. Nein? (Es ist eine theoretische Frage, da sie nach einer Antwort fragt - nicht nach der Maschine selbst ...)

A natural reference to a search for an intelligent machine would be the Golem... http://en.wikipedia.org/wiki/Golem#History

Sariel Har-Peled
quelle
0

I can answer your question with 100% certainty for a time period. If we consider the period from the seminal paper of Hartmanis and Stearns to any point in the future, the oldest problem in TCS which is still open is:

What is the minimum overhead needed for the simulation of deterministic TMs?

The first answer was T2(n) , where T(n) is the running time of the TM being simulated, with an improvement quickly provided by Hennie and Stearns to logT(n), which is the best current answer to the best of my knowledge.

This problem is still open and an improvement to it would improve many results, with the most important perhaps being the gap in the deterministic time hierarchy. However, research on the subject suggests that the logT(n) gap is necessary.

chazisop
quelle
1
these two statements seem contradictory to me: "This problem is still open" and "research on the subject shows that the logT(n) gap is necessary"
Sasho Nikolov
1
Ah thank you @SashoNikolov . A really bad choice of words. Corrected it to "suggests" , which is true, since the problem is really open. It's like P vs NP problem which is of course open, but most believe the two classes are not equal.
chazisop
1
This could use some clarification, for the benefit of those who do not know those papers in detail: What type of TM is being simulated? What type of machine is doing the simulation?
funkstar
I don't believe a clarification is necessary. That the model being used in the first paper is the multitape TM is a well known fact, since it contains some of the core definitions of TCS, plus it is explicitly mentioned in the title of the Hennie and Stearns paper.
chazisop
1
Your formulation of the open question is still too vague, in my opinion. Even though it is well known in the ToC community that Hartmanis, Hennie and Stearns work with multitape TMs, that merely makes your answer unhelpful to those in the many other fields of TCS. You should consider at least adding the qualifier "multitape" to the question. (And even then, you have the problem that Hartmanis and Stearns' simulation uses a 1-tape TM, whereas Hennie and Stearns' simulation uses a 2-tape TM.)
funkstar