Das Problem der Entscheidung, ob ein monotoner CNF einen monotonen DNF impliziert

14

Betrachten Sie das folgende Entscheidungsproblem

Eingabe : Ein monotoner CNF und ein monotoner DNF .& PSgr;ΦΨ

Frage : Ist eine Tautologie?ΦΨ

Definitiv können Sie dieses Problem in lösen, wobei die Anzahl der Variablen in und die Länge der Eingabe ist. Andererseits ist dieses Problem coNP-vollständig. Darüber hinaus zeigt eine Reduktion, die die CoNP-Vollständigkeit feststellt, auch, dass es für dieses Problem keinen -Zeitalgorithmus gibt, sofern SETH nicht ausfällt (Dies gilt für alle positiven ). Hier ist diese Reduktion. Sei ein (nicht monotoner) CNF und sei seine Variable. Ersetze jedes positive Vorkommen von durchn & Phi; & PSgr; l O ( 2 ( 1 / 2 - ε ) n p o l y ( l ) ) ε A x x yO(2npoly(l))nΦΨlO(2(1/2ε)npoly(l))εAxxyund jedes negative Vorkommen von durch . Machen Sie dasselbe für jede Variable. Der resultierende monotone CNF sei . Es ist leicht zu erkennen, dass erfüllt werden kann, wenn keine Tautologie ist. Diese Reduktion vergrößert die Anzahl der Variablen um den Faktor 2, was die oben erwähnte untere Grenze von (SETH-basiert) impliziert .z Φ A Φ y z 2 n / 2xzΦAΦyz2n/2

Es besteht also eine Lücke zwischen und Zeit. Meine Frage ist, ob ein besserer Algorithmus oder eine bessere Reduktion von SETH bekannt ist? 2 n2n/22n

Nur zwei Bemerkungen, die anscheinend mit dem Problem zusammenhängen:

  • Ein umgekehrtes Problem, ob ein monotoner DNF einen monotonen CNF impliziert, ist in der Polynomzeit trivial lösbar.

  • Interessanterweise kann das Problem der Entscheidung, ob Φ und \ Psi dieselbe FunktionΨ berechnen, durch Fredman und Khachiyan in quasi-polynomialer Zeit gelöst werden (On the Complexity of Dualization of Monotone Disjunctive Normal Forms, Journal of Algorithms 21 (1996), No. 3, S. 618–628, doi: 10.1006 / jagm.1996.0062 )

Sasha Kozachinskiy
quelle

Antworten:

6

Angenommen, SETH ist das Problem nicht in der Zeit für jedes lösbar . ε > 0O(2(1ϵ)npoly(l))ϵ>0


Lassen Sie mich zunächst zeigen, dass dies für das allgemeinere Problem gilt, bei dem und beliebige monotone Formeln sein können. In diesem Fall gibt es eine zeitlich mehrmalige Reduzierung von TAUT auf das Problem, bei dem die Anzahl der Variablen erhalten bleibt. Sei die Schwellenfunktion Unter Verwendung des Ajtai-Komlós-Szemerédi- kann durch eine monotone Formel in Polynomgröße geschrieben werden, die in time konstruiert werden kann .Ψ T n t ( x 0 , , x n - 1 ) T n t ( x 0 , , x n - 1 ) = 1ΦΨTtn(x0,,xn1)T n t poly(n)

Ttn(x0,,xn1)=1|{i<n:xi=1}|t.
Ttnpoly(n)

Bei einer gegebenen Booleschen Formel können wir De Morgan-Regeln verwenden, um sie in der Form wobei monoton ist. Dann ist genau dann eine Tautologie, wenn die monotonen Implikationen sind für jedes gültig , wobei ϕ ( x 0 , , x n - 1 , ¬ x 0 , , ¬ x n - 1 ) , ϕ ϕ ( x 0 , , x n - 1 ) T n t ( x 0 , ,ϕ(x0,,xn1)

ϕ(x0,,xn1,¬x0,,¬xn1),
ϕϕ(x0,,xn1)tn N i = T n - 1 t ( x 0 ,..., x i - 1 , x i + 1 ,, x n -
Ttn(x0,,xn1)ϕ(x0,,xn1,N0,,Nn1)
tn
Ni=Ttn1(x0,,xi1,xi+1,,xn1).

Für die Links-Rechts-Implikation sei eine Zuweisung, die , dh mit mindestens Einsen. Es gibt mit genau Einsen. Dann , also impliziert . Da dies eine monotone Formel ist, haben wir auch . Die Implikation von rechts nach links ist ähnlich.T n t t e 'e t e 'N i¬ x i e '& phiv; e '& phiv; ' ( x 0 , ... , x n - 1 , N 0 , ... , N n - 1 ) e ϕ ( x 0 , , x neTtnteeteNi¬xieϕeϕ(x0,,xn1,N0,,Nn1)eϕ(x0,,xn1,N0,,Nn1)


Lassen Sie mich nun zum ursprünglichen Problem zurückkehren. I werde die folgende zeigen: Wenn das Problem in der Zeit auflösbar ist , dann für jeden , -DNF-TAUE (oder dually, -SAT) lösbar in Zeit . Dies impliziert wenn SETH gilt.2δnpoly(l)kkk2δn+O(knlogn)poly(l)δ1

Nehmen wir also an, wir erhalten ein -DNF wobei für jedes . Wir teilen die n Variablen in n ' = n / b Blöcke der Größe b √ aufk

ϕ=i<l(jAixjjBi¬xj),
|Ai|+|Bi|kinn=n/b . Durch das gleiche Argumentwie oben,φist ein tautology wenn und nur wenn die Auswirkungen u < n ' T b T u ( x b u , ... , x b ( u + 1 ) - 1 ) i < l ( j A i x jj B i Nbk1nlognϕ gilt für jedenn'-Tupelt0,...,tn'-1[0,b], wobei für jedesj=bu+j',0j'<b, definieren wir Nj=T b - 1 t u (xbu,,xbu
()u<nTtub(xbu,,xb(u+1)1)i<l(jAixjjBiNj)
nt0,,tn1[0,b]j=bu+j0j<b Wir können T b t als monotonen CNF der GrößeO( 2 b )schreiben, daher ist die LHS von()ein monotoner CNF der GrößeO(n 2 b ). Auf der rechten Seite können wir N j schreiben
Nj=Ttub1(xbu,,xbu+j1,xbu+j+1,,xb(u+1)1).
TtbO(2b)()O(n2b)Njals monotone DNF der Größe . Somit kann unter Verwendung Verteilbarkeit, die jeweils disjunkt der RHS kann als monotonen DNF der Größe geschrieben werden OS ( 2 k b ) , und die ganze RHS ist eine DNF der Größe O ( l 2 k b ) . Daraus folgt, dass ( ) ein Beispiel für unser Problem der Größe O ( l 2 O ( k b ) ) in n Variablen ist. Angenommen, wir überprüfen die Gültigkeit in der Zeit O (O(2b)O(2kb)O(l2kb)()O(l2O(kb))n . Wir wiederholen diese Prüfung für alle b n ' Auswahl vont , wodurch die Gesamtzeit ist O ( ( b + 1 ) n / b 2 δ n + O ( k b ) l O ( 1 ) ) = O ( 2 δ n + OO(2δn+O(kb)lO(1))bnt wie beansprucht.
O((b+1)n/b2δn+O(kb)lO(1))=O(2δn+O(knlogn)lO(1))

Wir erhalten eine engere Verbindung mit der (S) ETH, indem wir die Version des Problems mit begrenzter Breite betrachten: Für bezeichnen k- MonImp die Einschränkung des Problems, wobei Φ ein k- CNF und Ψ ein a ist k -DNF. Die (S) ETH betrifft die Konstanten s kk3kΦkΨk

sk=inf{δ:k-SATDTIME(2δn)},s=sup{sk:k3}.
sk=inf{δ:k-MonImpDTIME(2δn)},s=sup{sk:k3}.
s3s4s1
sksk,
sk2sk.
b
sksbk+log(b+1)b,
s=s.
s=1sk>0k3
Emil Jeřábek unterstützt Monica
quelle
ΦΨTkn2nΩ(1/d)d2n
Tknd2nÖ(1/d). Siehe z . B. cstheory.stackexchange.com/q/14700 . Ich werde überlegen müssen, ob Sie sie monoton machen können, aber das klingt plausibel.
Emil Jeřábek unterstützt Monica
IN ORDNUNG. Erstens funktioniert die generische Konstruktion in der monotonen Einstellung einwandfrei: Wenn eine Funktion monotone Polygrößenformeln hat, hat sie Tiefenschärfe.d monotone Schaltkreise der Größe 2nÖ(1/d)pÖly(n) für jeden d2. Zweitens fürTkn Insbesondere ist es einfach, monotone Tiefen-3 Schaltkreise der Größe 2Ö(nLogn) durch Aufteilen der Eingabe in Blöcke der Größe Θ(nLogn).
Emil Jeřábek unterstützt Monica
Tatsächlich gibt es, wenn man diese Idee ein wenig weiter treibt, eine Antwort auf die ursprüngliche Frage: Unter der Annahme von SETH gilt die untere Schranke bereits für Φ monotoner CNF und Ψmonotone DNF. Ich werde es später aufschreiben.
Emil Jeřábek unterstützt Monica
Ich würde vermuten, dass Sie alle Variablen in etwa teilen können n Blöcke x1,xn und dann schreibe Tk1n(x1)Tknn(xn)ϕ für jeden k1++knn. Sie können verwenden2n-Größe CNF für jede Schwellenwertfunktion. Aber dann auf der rechten Seite haben Sie nicht DNF, sondern eine Formel der Tiefe 3 ...
Sasha Kozachinskiy