Härte von verrauschten Booleschen Funktionen

13

Sei f eine Boolesche Funktion von n Booleschen Variablen. Lassen g(x)=Tϵ(f)(x) ist der Erwartungswert von f(y) , wenn y gewonnen wird aus x durch jeweils mit einer Wahrscheinlichkeit von Koordinaten Flipping ϵ/2 .

Ich interessiere mich für Fälle, in denen es rechnerisch schwierig ist, g . Lassen Sie mich einen Begriff der "Annäherung" festlegen (es kann aber auch andere geben): Eine Boolesche Funktion h approximiert g wenn h(x)=1 wenn g(x)0.9 und h(x)=0 wenn g(x)0.1Ein Zählargument (basierend auf der Existenz positiver Ratenfehlerkorrekturcodes) scheint zu ergeben, dass es Boolesche Funktionen gibt, für die eine solche Approximation eine Schaltung mit exponentieller Größe erfordert. Aber die Frage ist, was passiert, wenn zunächst in NP oder in seiner Nachbarschaft liegt.f

Q1: Gibt es ein Beispiel für das durch die NP-Schaltung (oder den P-Raum) beschrieben wird, so dass jedes h NP-hart oder in einem schwächeren Sinne hart ist.fh

Um zu sehen , dass nicht immer einfach sein könnte (I Johan Hastad für nützliche Diskussion darüber danken) wir die Eigenschaft der Graphen der mit einer Clique der Größe betrachten kann n 1 / 4 , für zufällige Eingabe, ist es denkbar , dass es schwierig ist , zu Ermitteln Sie, ob eine große Clique vorhanden ist. Dies äußert sich jedoch darin, dass mehr als erwartete Cliquen mit der Größe log n im verrauschten Diagramm vorhanden sind. In diesem Fall ist jedes h wahrscheinlich schwer (aber nicht nachweisbar und nicht fürchterlich schwer, da quasi-polynomiale Schaltungen aussagen).hn1/4h

F2: Wie ist die Situation, wenn zunächst eine geringe Komplexität aufweist. ( A C 0 , monotone T C 0 , A C C usw.)fAC0TC0ACC

F3: Wie sieht es mit einigen grundlegenden Beispielen für Boolesche Funktionen aus? (Die Frage kann auch auf die reelle Funktion ausgedehnt werden.)

F4: Kann die obige Frage formal für das einheitliche (Turing-Maschine) Berechnungsmodell gestellt werden?

Update: In Anbetracht von Andys Antwort (Hallo, Andy) denke ich, dass die interessanteste Frage darin besteht, die Situation für verschiedene spezifische Funktionen zu verstehen.

Update Another question Q5 [Q1 für monotone Funktionen] (auch im Hinblick auf Andys Antwort). Wie ist die Situation, wenn monoton ist? Können wir noch robuste NP-Komplettfragen codieren>f

Gil Kalai
quelle
imho ist diese frage zur schaltungsannäherung verwandt. Ihre Frage scheint der Frage P / Poly vs NP ähnlich zu sein.
VZN

Antworten:

14

Für Frage 1 lautet die Antwort Ja und kann wie folgt angezeigt werden. (Ich werde auch implizit eine positive Antwort auf Q4 skizzieren, da das Argument einheitlich ist und alle Eingabelängen gleichzeitig behandelt.)

Korrigieren Sie jede NP-vollständige Sprache und eine Familie guter binärer Fehlerkorrekturcodes (mit einer Rate von 1/4 und einer Korrektur aus einem Bruchteil von Fehlern, sagen wir). Es sei E n c n : { 0 , 1 } n{ 0 , 1 } 4 n die Codierungsfunktion für die Länge n ; Wir verwenden einen solchen Code, bei dem E n c = { E n c n } durch einen Algorithmus mit einheitlicher Polynomzeit berechenbar ist.LEncn:{0,1}n{0,1}4nnEnc={Encn}

Definieren Sie als die Menge der Zeichenfolgen z , die sich höchstens in der Entfernung von .05 | befinden z | aus einem Codewort y E n c ( L ), das ein Element von L codiert . Es ist zu beachten, dass L ' in NP ist, wie Sie das nahegelegene Codewort, das decodierte Wort und das NP-Zertifikat für die Zugehörigkeit des decodierten Wortes in L erraten und überprüfen können . Lz.05|z|yEnc(L)LLL

Dann lautet die Behauptung, dass jede "Annäherung" von in Ihrem Sinne NP-hart für ε = .01 ist . Wenn wir ein gültiges Codewort y = E n c ( x ) mit einer Länge von 4 n betrachten , dann wird es mit der Wahrscheinlichkeit 1 - o ( 1 ) über eine zufällige ε- gestörte Version y ' von y höchstens mit y in nicht übereinstimmen a .05 Bruchteil von Koordinaten und wird daher mit keinem anderen Codewort von E n c übereinstimmenLε=.01y=Enc(x)4n1o(1)εyyy in einemBruchteil vonmehr als 0,05 von Koordinaten. Für ein solches y 'haben wir y 'L ', wenn x L ist . Wenn also h in Ihrem Sinneeine Annäherung an die ε- geglättete Version von L ′ ist , müssen wir h ( y ) = L ( x ) haben . Da E n c effizient berechenbar ist, können wir die Mitgliedschaftsfragen für L effizientauf diejenigen für h reduzieren. SoEncn.05yyLxLhεLh(y)=L(x)EncLh ist NP-hart.h

Zwei Notizen:

(1) Fehlerkorrekturkodierungen von NP-Instanzen wurden bereits in mehreren Veröffentlichungen verwendet, insbesondere in
D. Sivakumar: Über Mitglieder-Vergleichssätze. J. Comput. Syst. Sci. 59 (2): 270 & ndash; 280 (1999).

(2) Das obige Argument sagt natürlich nichts über die Durchschnittskomplexität eines NP-Problems aus, da die Fehlerkorrektur von Fall zu Fall angewendet wird.

Andy Drucker
quelle
8
Die Software lässt mich meine Antwort nicht mit "Hi Gil" beginnen, und ich bin ein bisschen durch diese Ebene des Mikromanagements geschlichen.
Andy Drucker
2
Dies liegt daran, dass Ihre Antwort nicht mit "Hi Gil" beginnen sollte . Es ist keine persönliche E-Mail, es ist ein Beitrag auf einer öffentlichen Website. Natürlich sind die Gleichen von Ihnen nicht diejenigen, auf die dies abzielt. Es sind eher neue Benutzer, die diese Konventionen, die die Software steuern soll, nicht kennen.
Yuval Filmus
1
Meiner Meinung nach ist es in Ordnung zu erkennen, wenn jemand als Antwort auf den Beitrag eines anderen schreibt. Dies ist in vielen Online-Einstellungen normal und positiv. Ich habe versucht, dies so kurz wie möglich zu machen, und zwar anhand meiner persönlichen Adresse. sehe nichts falsch daran.
Andy Drucker
2
Schöne Konstruktion! Ich habe eine Frage: Sei f die Indikatorfunktion von L 'und h wie in Gils Frage. Ihr Argument zeigt nun, dass h mit f für y übereinstimmt, die zulässige Codewörter sind. Aber wie wäre es mit ys, die keine legalen Codewörter sind?
Oder Meir
2
Kann man so etwas mit monotone umsetzen ? f
Gil Kalai