Wie kann man mit einem alten SAT-Solver einen neuen entdecken, wie in The Golden Ticket beschrieben?

In Lance Fortnows Buch The Golden Ticket erwähnt er, dass Sie einen Polynom-Zeit-Algorithmus für ein NP-vollständiges Problem verwenden können, um einen schnelleren Algorithmus zu finden. Können Sie mir sagen, wie das gemacht wird? Und wenn dies erledigt ist, können Sie den neuen Algorithmus verwenden, um eine noch schnellere ad infinitum bis zu einem festen Punkt zu entdecken . Unten ist das genaue Zitat aus dem Buch:

"Also, was fragst du einen Geist, der dir nur einen Wunsch erfüllt?" sagte der Berater.

"Ich habe keine Ahnung", antwortete Steve.

"Sie fragen nach einem Geist, der alle Ihre Wünsche erfüllt."

Die sprichwörtliche Glühbirne ging in Steves Kopf aus. Er wusste, dass es irgendwo einen besseren Algorithmus geben musste, um Cliquenprobleme zu lösen, aber er konnte es nicht alleine herausfinden. Aber er hatte den Geist, den Tsinghua-Code, der schnell nach einer exponentiellen Anzahl von Möglichkeiten suchen konnte. Also schrieb er ein Programm, das die Tsinghua-Routinen verwendete, um nach einem besseren Algorithmus für NP-Probleme zu suchen. Er erhielt die Erlaubnis, die Computerressourcen des Nationalen Zentrums für Supercomputing-Anwendungen (NCSA) an der Universität von Illinois zu nutzen. Nach wochenlanger Verarbeitungszeit zahlte sich seine Arbeit ein wenig aus und fand einen neuen Algorithmus, der eine 5-prozentige Verbesserung gegenüber dem Tsinghua-Code aufwies - gut genug für eine Forschungsarbeit, aber nicht genug, um eine echte Wirkung zu erzielen.

Sein Berater sagte einfach: "Versuchen Sie es erneut mit dem neuen Code."

Also benutzte Steve seinen neuen Code, um einen noch schnelleren Algorithmus für NP-Probleme zu finden. Einige Wochen später hatte er eine 20-prozentige Verbesserung.

Aber sein Berater war nicht beeindruckt. "Versuche es noch einmal."

Steve antwortete: "Warum richte ich den Computer nicht einfach so ein, dass er es automatisch mit dem neuen Code versucht, den er findet?"

Der Berater warf diesen Blick zu, der einem Schüler sagte, er habe Erleuchtung erlangt oder zumindest das Offensichtliche erkannt.

Steve kehrte in sein Büro zurück und begann mit dem kniffligen Prozess des Schreibens von Code, der nach schnellerem Code sucht. Anschließend verwendete er diesen schnelleren Code, um noch schnelleren Code zu finden und diesen Prozess fortzusetzen, bis keine weitere Verbesserung mehr festgestellt werden konnte.

Konzentrieren Sie sich jetzt auf SAT. MiniSAT ist ein schneller SAT-Löser, allerdings nicht bis zur Polynomzeit.

Wie kann man mit MiniSAT einen neuen SAT-Solver mechanisch entdecken?

algorithms np-complete p-vs-np sat-solvers Zirui Wang
quelle

@ZiruiWang - Das Finden eines Algorithmus aus einem festen Satz von Kandidatenalgorithmen ist normalerweise a

Σ_{2}

$\Sigma_2$ /.

P i_{2}

$Pi_2$ Problem eher als ein NP-vollständiges Problem. Der Autor hätte das bedeuten können (sie können durch verschachtelte SAT-Löser gelöst werden). Alternativ könnte der Autor beabsichtigt haben, bestimmte Parameter bestehender Algorithmen zu optimieren.

DCTLib

Der Satz von Algorithmen ist unendlich. Sie können einen Algorithmus nur mit einem SAT-Solver finden, wenn Sie den Suchraum korrigieren. Der Suchraum ist dann der Raum der Kandidatenalgorithmen. Das Verschachteln von SAT-Lösern zum Auffinden neuer Algorithmen wird in diesem

Dokument

"Einen Algorithmus finden" ist im Wesentlichen eine Synthese. Es ist in Sigma_2, weil wir überprüfen wollen (1), ob es eine Implementierung gibt, so dass (2) für alle Eingaben die Implementierung korrekt funktioniert. Der Teil nach (2) ist im Wesentlichen ein Co-NP-Problem. Sie können es als verschachtelt bezeichnen, wenn der eine SAT-Löser eine Lösung findet und der andere SAT-Löser verwendet wird, um sie zu überprüfen. Ist dies nicht der Fall, werden Klauseln zur ersten hinzugefügt. Der erste SAT-Löser wiederholt somit seine Arbeit, bis der zweite mit der Lösung einverstanden ist. Daher wird in einer SAT-Prozedur ein SAT-Löser aufgerufen.

DCTLib

@DCTLib Die Annahme ist, dass P = NP, also PH zusammenbricht und alles zu P. vereinfacht

Zirui Wang

@DCTLib, viele tolle Kommentare dort. Möchten Sie eine vollständige Antwort schreiben?

Antworten:

Wahrscheinlich können Sie mit einem SAT-Solver keinen anderen SAT-Solver finden, es sei denn, etwas Überraschendes passiert.

Wenn P = NP, dann können Sie. Wenn P = NP, dann kollabiert die Polynomhierarchie (dh P = PH), so dass es für jedes Problem in PH einen Polynomzeitalgorithmus gibt . Das Problem der Frage, ob es einen schnelleren SAT-Lösungsalgorithmus gibt, ist im Wesentlichen a $\Sigma_2$ Problem, das Teil der Polynomhierarchie ist; Wenn die Polynomhierarchie zusammenbricht, gibt es für jedes Problem in PH und damit für jedes Problem in einen Polynom-Zeit-Algorithmus $\Sigma_2$ . Somit können Sie in Polynomzeit nach einem besseren SAT-Löser suchen, wenn P = NP.

Die meisten Forscher gehen jedoch davon aus, dass P nicht gleich NP ist. Daher ist diese Aussage höchstwahrscheinlich umstritten und in der Praxis wahrscheinlich nicht hilfreich.

Wenn P nicht gleich NP ist, funktioniert diese Argumentation nicht. Tatsächlich erwarten das viele Forscher $\Sigma_2$ ist noch schwieriger als NP (es gibt Probleme in $\Sigma_2$ das ist schwieriger als jedes Problem in NP), daher wäre es überraschend, wenn es eine einfache Reduzierung gäbe, um das Problem "Finde mir einen schnelleren SAT-Löser" als Instanz von SAT auszudrücken. Insbesondere können SAT-Löser SAT oder jedes andere Problem in NP lösen - aber auf jeden Fall nur Probleme in NP. Wenn (wie wir vermuten) $\Sigma_2$ ist schwieriger als NP, dann können SAT-Löser Probleme nicht lösen $\Sigma_2$ .

Natürlich wissen wir es nicht wirklich. Es ist immer möglich, dass die konventionelle Weisheit falsch ist und dass wir morgen feststellen, dass P tatsächlich gleich NP ist. Das wäre eine große Überraschung, aber wir können es nicht vollständig ausschließen.

Das Goldene Ticket versucht ein tieferes Verständnis dafür zu vermitteln, warum Komplexitätstheoretiker das P vs NP-Problem für so wichtig und grundlegend halten. Ein Teil davon besteht darin, kontrafaktische Welten und kontrafaktische Annahmen zu untersuchen, von denen wir vermuten, dass sie wahrscheinlich falsch sind, um zu sehen, welche Konsequenzen sie haben würden.

Oder um es anders zu erklären:

Das Problem ist, dass das Finden eines besseren SAT-Lösers a ist $\exists \forall$ Art der Aussage. Die Aussage hat die Form $\exists A \forall x . P(A,x)$ , wo $P(A,x)$ ist die Aussage, dass $A$ ist schnell und löst die SAT-Instanz korrekt $x$ . Solche Aussagen können mit einem SAT-Solver nicht gelöst werden. SAT-Löser können Probleme der Form lösen $\exists x. Q(x)$ . Jedoch, $\exists \forall$ Aussagen sind schwieriger als $\exists$ Aussagen. Dies ist im Grunde der Unterschied zwischen $\Sigma_2$ und NP.

DW
quelle

Warum kann ein SAT-Löser a nicht lösen?

Σ_{2}

$\Sigma_2$ Aussage? Es ist immer noch Exponentialzeit. Die Schwierigkeit liegt in der Codierung.

Zirui Wang

@ZiruiWang, ich habe den vierten Absatz meiner Antwort bearbeitet, um zu erklären, warum dies expliziter ist. SAT-Löser können nicht alle Exponentialzeitprobleme lösen (es sei denn, NP = EXPTIME, von dem wir vermuten, dass dies nicht der Fall ist).

@ZiruiWang Sie können wahrscheinlich viele Probleme als SAT codieren, aber sie sind möglicherweise nicht polynomisch lang. SAT trifft auf harte Fälle für Polynomeingaben, daher wird es wahrscheinlich nicht funktionieren, wenn es auf einer exponentiell großen Eingabe ausgeführt wird.

Jmite