Ist das Einbetten einer Lösung für SAT möglich?

Ich interessiere mich für "harte" Einzelfälle von NP-vollständigen Problemen.

Ryan Williams diskutierte das SAT0-Problem in Richard Liptons Blog . SAT0 fragt, ob eine SAT-Instanz die spezifische Lösung hat, die aus allen Nullen besteht. Dies brachte mich zum Nachdenken über die Erstellung von SAT-Instanzen, die wahrscheinlich "schwer" sind.

Betrachten Sie eine SAT-Instanz mit m Klauseln und n Variablen, wobei α = m / n "groß genug" ist, in dem Sinne, dass sie in den Bereich jenseits des Phasenübergangs fällt, in dem fast alle Instanzen unbefriedigend sind. Sei x eine zufällige Zuordnung zu den Werten von ϕ .$\phi$$m$$n$$\alpha = m/n$$x$$\phi$

Ist es möglich, zu ändern , um eine neue Instanz ϕ | zu erhalten ? x , so dass ϕ | x ist "weitgehend ähnlich" zu ϕ , so dass x eine zufriedenstellende Zuordnung für ϕ | ist x ?$\phi$$\phi|x$$\phi|x$$\phi$$x$$\phi|x$

Beispielsweise könnte man versuchen, jeder Klausel ein zufällig ausgewähltes Literal aus der Lösung hinzuzufügen, das in der Klausel noch nicht vorkommt. Dies garantiert, dass eine Lösung ist.$x$

Oder ist dies hoffnungslos und führt zu einem schnellen Algorithmus zum Auffinden der "versteckten" Lösung, wie in der folgenden kürzlich erschienenen Veröffentlichung beschrieben?

• Uriel Feige und Dorit Ron, Suche nach versteckten Cliquen in linearer Zeit , DMTCS proc. AM, 2010, 189–204.

Ich bin mir der Diskussion von Cook und Mitchell und der Arbeit, auf die sie sich beziehen, bewusst. Ich konnte jedoch nichts darüber finden, was mit der Struktur einer Formel passiert, wenn man versucht, eine zufriedenstellende Aufgabe explizit darin einzubetten. Wenn dies Folklore ist, wären Hinweise sehr willkommen!

• Stephen A. Cook und David G. Mitchell, Finden harter Beispiele für das Problem der Erfüllbarkeit: Eine Umfrage , DIMACS-Reihe in diskreter Mathematik und theoretischer Informatik 35 1–17, AMS, ISBN 0-8218-0479-0, 1997. ( PS )

Sie können jede Formel und in die Formel φ ∨ ψ x ändern, wobei ψ x eine "harte" SAT-Instanz ist, deren einzige Lösung x ist . Eine Möglichkeit, eine solche Formel zu konstruieren, ist die Verwendung der Kryptographie: Wenn f : { 0 , 1 } n → { 0 , 1 } n eine Einwegpermutation ist und wir x zufällig auswählen und y = f ( x ) setzen , dann eine kann y in eine SAT-Formel umwandeln, so dass $\varphi$$\varphi \vee \psi_x$$\psi_x$$x$$f:\{0,1\}^n\rightarrow \{0,1\}^n$$x$$y=f(x)$$y$$x$ist seine einzige Lösung und somit entspricht das Finden von der Invertierung von f . (Wir müssen dafür sorgen , dass dieses x zufällig ist, aber dies wird trotzdem angenommen, wenn wir der Meinung sind, dass es schwierig sein sollte , x zu finden.)$x$$f$$x$$x$

$\frac{m}{n}> 4.3$

$x$$n$$m$$k$$p = \frac{1}{2}$$x$$\phi|x$$\phi$$\phi|x$$x$$l$$l$$\phi$$\phi|x$$\phi$$\phi|x$

$\phi|x$$\phi$

$\phi$$x$

1. $\phi$$x$$x$

2. $m_x$$m_x$$x$$x$

$x$$x$$x$

Der beste Weg, um mir bekannte harte Instanzen von NP-vollständigen Problemen zu generieren, besteht darin, die Cook-Zuordnung zu verwenden, um sorgfältig ausgewählte Instanzen bestimmter anderer harter NP-Probleme (wie das Problem des diskreten Logarithmus oder die ganzzahlige Faktorisierung) auf SAT zu reduzieren. Dies sind dieselben "harten Probleme", die von Mathematikern verwendet werden, um die kryptografische Sicherheit in Protokollen wie RSA und Diffie-Hellman zu gewährleisten.