Gibt es einen Algorithmus, der nachweislich existiert, obwohl wir nicht wissen, was er ist?

21

In der Mathematik gibt es viele Existenzbeweise, die nicht konstruktiv sind, so dass wir wissen, dass ein bestimmtes Objekt existiert, obwohl wir nicht wissen, wie wir es finden können.

Ich suche nach ähnlichen Ergebnissen in der Informatik. Insbesondere: Gibt es ein Problem, das wir beweisen können, dass es entscheidbar ist, ohne einen Algorithmus dafür zu zeigen? Dh wir wissen, dass es durch einen Algorithmus gelöst werden kann, aber wir wissen nicht, wie der Algorithmus aussieht?

Erel Segal-Halevi
quelle
5
Es gibt eine triviale Antwort. Nehmen Sie eine beliebige Ja / Nein-Frage, deren Antwort unbekannt ist, wie "ist zufällig", dann ist die Frage entscheidbar, nur wissen wir noch nicht, welcher der beiden möglichen Algorithmen korrekt ist. π
Hendrik Jan
6
Grundsätzlich Duplikat von tcs.se Frage gibt es nicht-
vzn
1
@babou In der Tat: Eine Frage mit einer eindeutigen Antwort ist entscheidend. Hier scheint Unwissenheit der Punkt zu sein, es ist ein Fall von "Weiß nicht" aus der Frage, obwohl nur "Weiß nicht jetzt ". Sobald wir herausgefunden haben, ob zufällig ist oder nicht, müssen wir nach einem anderen Beispiel suchen. Ihre Antwort unten ist natürlich viel besser! Es ist eine Form von "weiß nicht", die von Natur aus "wird es nie wissen" ist. π
Hendrik Jan
1
@HendrikJan: Und diese Prozedur nennen wir einen Algorithmus in CS. Aber am Beispiel des Halteproblems können wir nicht einmal beweisen, dass ein Algorithmus existiert!
MSalters
1
Weitere interessante Beispiele finden Sie hier: cstheory.stackexchange.com/questions/4777/…
Erel Segal-Halevi

Antworten:

14

Im einfachsten Fall kenne ich einen Algorithmus, der existiert, obwohl nicht bekannt ist, welcher Algorithmus sich auf Automaten mit endlichen Zuständen bezieht.

Der Quotient einer Sprache L 1 durch eine Sprache L 2 definiert ist als L 1 / L 2 = { x | y L 2  derart , daß  x y L 1 } .L1/L2L1L2L1/L2={xyL2 such that xyL1}

Es ist leicht zu beweisen, dass reguläre Mengen unter einem Quotienten durch eine beliebige Menge geschlossen werden. Mit anderen Worten, wenn regulär ist und L 2 willkürlich ist (nicht notwendigerweise regulär), dann ist L 1 / L 2 auch regulär.L1L2L1/L2

Der Beweis ist ganz einfach. Sei eine FSA, die die reguläre Menge R akzeptiert , wobei Q und F jeweils die Menge von Zuständen und die Menge von akzeptierenden Zuständen sind, und sei L eine beliebige Sprache. Lassen F ' = { q Q | y LM=(Q,Σ,δ,q0,F)RQFL ist die Menge von Zuständen, aus denen ein Endzustand erreicht werden kann, indem ein String aus L akzeptiert wird.F={qQyLδ(q,y)F}L

Der Automat , das sich von M nur in seinem Satz F ' von Endzuständen erkennt präzise R / L . (Oder siehe Hopcroft-Ullman 1979, Seite 62 für einen Beweis dieser Tatsache.)M=(Q,Σ,δ,q0,F)MFR/L

LFFQR2|Q|

Dies ist ein Beispiel für das, was manchmal als beinahe konstruktiver Beweis bezeichnet wird, dh ein Beweis dafür, dass eine von einer endlichen Anzahl von Antworten die richtige ist.

Ich nehme an, eine Erweiterung davon könnte ein Beweis dafür sein, dass eine der unzähligen Antworten die richtige ist. Aber ich kenne keine. Ich kenne auch keinen rein nicht konstruktiven Beweis dafür, dass ein Problem entscheidbar ist, zum Beispiel nur mit Widersprüchen.

babou
quelle
1
RLL
Vielen Dank. Dies ist meine Lieblingsantwort, weil die entscheidbare Sprache unendlich ist.
Erel Segal-Halevi
@babou, mein Fehler, ich habe falsch gelesen, was du geschrieben hast. Meine Schuld - tut mir leid. Ich habe Ihren Beitrag bearbeitet, um den Teil zu machen, den ich hoffentlich cleraer missverstanden habe.
DW
@ DW Ich bin amüsiert, dass du ein Problem hattest, aber es passiert mir auch. Aber vielleicht hätte ich klarer sein sollen. Dies war nicht beabsichtigt. Das zu sagen, weil einige Mathematiker denken, es sei eleganter, kryptisch zu sein. Danke für die Bearbeitung.
Babou
12

Berücksichtigen Sie dieses Problem, um Hendricks ursprünglichen Kommentar zu erweitern

n0nπ

Dieses Problem ist entscheidend, da einer von zwei Fällen erhalten werden kann:

  1. NπN
  2. nπn

In Fall (1) wäre ein Entscheidungsalgorithmus für das Problem einer von

n>N

und im Fall (2) wäre der Algorithmus

Antworten Sie mit "Ja".

Offensichtlich ist jeder von diesen ein Entscheidungsalgorithmus; wir wissen nur nicht welche. Das genügt, da decidability aber erfordert nur die Existenz eines Algorithmus, nicht die Angabe , welche Algorithmus.

Rick Decker
quelle
+1 Dies ist ein einfaches Beispiel, an das ich mich an meinen Professor für Rechenfähigkeit und Logik erinnere. Es ist mein Paradebeispiel, da es nicht viel Domänenwissen erfordert und daher einfach zu vermitteln ist.
Joshua Taylor
1
Für alternative Formulierungen siehe auch hier .
Raphael
2

Hier ist eine Nichtantwort. Ich poste, weil ich glaube, dass es lehrreich ist, weil ich ursprünglich das Gegenteil behauptet habe und acht Leute sich genug einig waren, um zu stimmen, bevor @sdcwc auf den Fehler hinwies. Ich wollte meine erste Antwort nicht einfach bearbeiten, weil ich nicht sicher bin, ob es so viele Leute gegeben hätten, wenn sie gewusst hätten, dass es falsch war.

SS

HH

David Richerby
quelle