"Fast einfache" NP-Komplettprobleme

Nehmen wir an, eine Sprache ist P- dichtennah, wenn es einen polynomialen Zeitalgorithmus gibt, der für fast alle Eingaben korrekt entscheidet . $L$ $L$

Mit anderen Worten, es gibt ein P , so dass verschwindet, was Dies bedeutet auch, dass bei einer einheitlichen Zufallseingabe der Polyzeitalgorithmus für die richtige Antwort für mit einer Wahrscheinlichkeit nahe 1 liefert . Daher ist es sinnvoll, fast einfach anzuzeigen . $A\in$ $L\Delta A$

lim_{n \to \infty} \frac{| (L Δ A) \cap {0, 1}^{n} |}{2^{n}} = 0.

$\lim_{n\rightarrow\infty} \frac{|(L\Delta A) \cap \{0,1\}^n|}{2^n}=0.$

A

$A$

L

$L$

L

$L$

Beachten Sie, dass $L\Delta A$ nicht dünn sein muss. Wenn es beispielsweise $2^{n/2}$ $n$ Bit-Strings enthält, verschwindet es immer noch (mit einer exponentiellen Rate), da $2^{n/2}/2^n=2^{-n/2}$ .

Es ist nicht schwer (künstlich) NP- vollständige Probleme zu konstruieren, die gemäß der obigen Definition P -dicht sind. Sei $L$ beispielsweise eine beliebige NP- vollständige Sprache und definiere $L^2=\{xx\,|\, x\in L\}$ . Dann behält $L^2$ die NP- Vollständigkeit bei, hat aber höchstens $2^{n/2}$ $n$ Bit-Ja-Instanzen. Daher entscheidet der einfache Algorithmus, der auf jede Eingabe mit "Nein" antwortet, bei fast allen Eingaben korrekt mit $L^2$ ; es wird nur bei einem $\leq 1-2^{-n/2}$ Bruchteil von $n$ Bit-Eingaben fehlerhaft sein.

Andererseits wäre es sehr überraschend, wenn alle NP- vollständigen Probleme P- dichteschließend wären. Es würde bedeuten, dass in gewissem Sinne alle NP- vollständigen Probleme fast einfach sind. Dies motiviert die Frage:

Unter der Annahme , P $\neq$ NP , die einige sind natürliche NP -komplette Probleme , die sind nicht P -Dichte-close?

cc.complexity-theory ds.algorithms complexity-classes np-complete Andras Farago
quelle

Da Heuristica nicht ausgeschlossen ist, gibt es nicht einmal ein nicht notwendigerweise natürliches Problem , für die P ≠ NP bekannt ist , implizieren , dass das Problem nicht fast in P. ist

Ich glaube, dass die Postkorrespondenzprobleme ein gutes Kandidatenproblem sind. Es ist selbst für gleichmäßig zufällige Fälle schwierig und daher im Durchschnitt schwierig.

Mohammad Al-Turkistany,

Zu Ihrer Information: Ihre Wahl der Nomenklatur steht im Widerspruch zu einer bestehenden Nomenklatur, obwohl sie natürlich ist: Die Klasse Almost-P besteht aus den Sprachen L, sodass Maß 1 hat. Das könnte Sie auch interessieren wissen, dass die spärliche Version Ihrer Definition bereits verwendet wurde und Verbindungen zu mehreren anderen Ideen hat, siehe P-close . In Anbetracht der Definition von P-Close ist P-Density-Close oder P-Close-Genug ein guter Name für Ihr Konzept :).

{A : L \in P^{A}}

$\{A : L \in P^A\}$

Joshua Grochow

Andererseits ist das Entscheidungsproblem " Graph Coloration " vermutlich ein Kandidat für ein solches Problem.

$\;$

Ich bin nicht überzeugt, dass dies die richtige Definition ist. Wenn die Dichte von verschwindet, ist es "fast einfach" über eine beliebige Trivialsprache , egal wie schwer es tatsächlich ist. Es ist jedoch schwierig, natürliche harte Sprachen über dem Alphabet mit einer Dichte zu präsentieren, die allein aufgrund der Codierung nicht verschwindet. Sollte der Schnittpunkt nicht mit den gültigen Eingaben der Größe (dies ist also ein Versprechungsproblem), sondern mit allen Zeichenfolgen? Ansonsten muss vor allem die Frage beantwortet werden: Gibt es eine boolesche Codierung für eine NP-harte Sprache mit einer Dichte, die nicht verschwindet?

L

$L$

A

$A$

{0, 1}

$\{0,1\}$

n

$n$

András Salamon

Ich habe untersucht, ob es eine allgemein akzeptierte Hypothese in der Komplexitätstheorie gibt, die impliziert, dass es eine NP- vollständige Sprache geben muss , die in der Polynomzeit nicht für fast alle Eingaben akzeptiert werden kann (wie in der Frage definiert).

Interessanterweise scheinen die meisten "Standard" -Hypothesen dies nicht zu implizieren. Das heißt, es scheint nicht zu folgen (es sei denn, ich habe etwas übersehen) aus P NP , P BPP , NP coNP , E NE , EXP NEXP , NP PSPACE , NP EXP , NP P / poly, PH bricht nicht zusammen usw. $\neq$ $=$ $\neq$ $\neq$ $\neq$ $\neq$ $\neq$ $\not\subseteq$

Auf der anderen Seite fand ich eine, etwas weniger standardisierte Hypothese, die die Existenz des gesuchten NP- vollständigen Problems impliziert , wenn auch kein natürliches. In der Theorie des ressourcengebundenen Maßes lautet die grundlegende Hypothese, dass NP keine Messung Null hat, die mit NP . Informell bedeutet dies, dass NP- Sprachen innerhalb von E keine vernachlässigbare Teilmenge bilden. Einzelheiten finden Sie in einer Umfrage hier . In dieser Theorie beweisen sie unter anderem, dass NP die Existenz eines P impliziert $p$ $\mu_p($ $)\neq 0$ $\mu_p($ $)\neq 0$ -bi-immune Sprache in NP . Eine Sprache ist P- bi-immun, wenn weder noch sein Komplement eine unendliche Teilmenge in P haben . Eine solche Sprache erfüllt unsere Anforderungen in starker Weise. $L$ $L$

Es bleibt jedoch weiterhin unklar, ob es ein Beispiel gibt, das ein natürliches Problem darstellt.

Andras Farago
quelle

Bi-Immunität ist auch viel stärker als Ihre Bedingung und hängt mit der allgemeineren Verwendung von "fast allen" in der Theorie der strukturellen Komplexität zusammen, nämlich "für alle bis auf endlich viele" ...

Joshua Grochow

@JoshuaGrochow Ich stimme zu, aber es scheint, dass P-Bi-Immunität in gewissem Sinne eine zu starke Unlösbarkeit bedeutet. Es scheint nicht bei natürlichen NP-vollständigen Problemen aufzutreten. Es ist für mich überraschend, dass es anscheinend kein Ergebnis gibt, das lediglich Bedingungen für die Existenz einer "fast überall schwach" hartnäckigen NP-vollständigen Sprache bietet. Mit "fast überall schwach" meine ich, dass die Bedingung "alles bis auf ein Minimum viele" durch "alles bis auf ein Minimum viele" ersetzt wird. Das könnte sich besser auf das beziehen, was in der Praxis tatsächlich vorkommt.

Andras Farago

Ist bekannt, dass NP p-messbar ist?

@ RickyDemer Soweit ich weiß, ist nicht bekannt, ob NP p-messbar ist.

Andras Farago

"Fast einfache" NP-Komplettprobleme

Antworten: