Gibt es einen Kandidaten für ein natürliches Problem in ?

Ich möchte wissen, ob Ungleichmäßigkeit die Rechenfunktionen in der Praxis unterstützt. Es ist leicht zu zeigen, dass es Funktionen in , eine nicht berechenbare Funktion und die Sprache { } zu berücksichtigen , die eindeutig einfache uneinheitliche Schaltungen aufweist , ist aber überhaupt nicht einheitlich berechenbar, aber das ist nicht die Art von Funktionen, die mich interessieren. $P/poly - P$ $f$ $0^{f(n)}:n\in \omega$

Gibt es eine Funktion, von der wir wissen, dass sie nicht einheitlich berechnet werden kann, aber wir wissen nicht, ob sie einheitlich berechnet werden kann (oder zumindest zu beweisen, dass sie nicht einheitlich berechnet werden kann, ist nicht offensichtlich)?

Wie kann eine Uneinheitlichkeit von Schaltkreisen für die Berechnung von Funktionen verwendet werden, von denen nicht bekannt ist, dass sie einheitlich berechenbar sind (mit nahezu der gleichen Menge an Ressourcen)?

Bitte beachten Sie, dass ich keine pathologischen Funktionen wie die oben genannten, nicht berechenbaren Funktionen haben möchte, sondern natürliche Funktionen, an denen die Menschen wirklich interessiert sind und die plausibel einheitlich berechnet werden können oder hätten können.

Edit: Ich weiß, dass . Daher ist eine Antwort, die kein Ergebnis einer Derandomisierung ist, für mich interessanter. $BPP \subseteq P/poly$

Edit 2: Wie András Salamon und Tsuyoshi Ito gesagt haben in ihren Antworten, , und es gibt interessante Probleme in , die nicht in sein sind dafür bekannt , so formal haben sie beantwortet , was ich gefragt, aber das hilft nicht bei dem, woran ich wirklich interessiert bin, da der Grund, dass sie in sind, die Möglichkeit ist, eine spärliche Sprache hart in die Schaltung zu codieren. Eine Sprache, die nicht spärlich ist, wäre interessanter. $Sparse \subset P/poly$ $Sparse$ $P$ $P/poly$

cc.complexity-theory uniformity Kaveh
quelle

@ András Salamon, @Tsuyoshi Ito: Danke. Was mich interessiert, ist zu verstehen, wie Ungleichmäßigkeit bei der Berechnung von Funktionen helfen kann. Die Tatsache, dass spärliche Sprachen in hilft nicht weiter, sie sind in einfach weil wir sie in die Schaltung "hart codieren" können. Ich hätte meiner Frage die Anforderung hinzufügen müssen, dass "die Sprache nicht trivial in ".

P / p o l y

$P/poly$

P / p o l y

$P/poly$

P / p o l y

$P/poly$

Kaveh

Antworten:

Ich weiß nicht, ob dies Ihren Anforderungen entspricht, aber der Blogbeitrag von Bill Gasarch im Juli 2010 fragt nach Sprachen in SPARSE ∩NP, die nicht in P vorkommen, und gibt ein Beispiel von Ramsey Theory. Solche Sprachen gehören zu (P / poly) ∩NP.

In Verbindung damit ist für jede Sprache L ∈NP die Sprache T _L = {1 ⁿ : L enthält einen String der Länge n } in TALLY ∩NP ⊆ SPARSE ∩NP (P / poly) ∩NP. Je nach Wahl der Sprache L , T _L kann keinen offensichtlichen Grund, P. zu gehören

Tsuyoshi Ito
quelle

Tsuyoshi Itos elegant spärliche Formulierung in einer anderen Antwort sagt dies nicht ausdrücklich aus, aber es lohnt sich vielleicht darauf hinzuweisen: Jede spärliche Sprache ist in P / Poly. Dann ist auch jede Zählsprache in P / poly (da jede Zählsprache spärlich ist).

Eine Möglichkeit, "natürliche" Sprachen in P / poly zu finden, aber nicht in P, besteht darin, nach "harten", spärlichen Sprachen zu suchen. Wie Sie betonen, sind die "härtesten" diejenigen, die unentscheidbar sind, wenn sie auf spärliche Weise codiert werden, beispielsweise in Unary. Im Allgemeinen ist die unärkodierte Version einer Sprache außerhalb von EXP dann außerhalb von P. (Wenn nicht, betrachten Sie die Exponentialzeit-Turing-Maschine, die die unärkodierte Kodierung generiert, die mit der Maschine zusammengesetzt ist, die die resultierende unärkodierte Sprache rechtzeitig löst Dies ist in der unären Codierung ein Polynom. Dies ist exponentiell in der Größe der ursprünglichen Instanz. Die gesamte Maschine läuft dann in exponentieller Zeit.) Eine handliche 2-EXP-vollständige Sprache könnte dann Ihrem Geschmack als "natürliches" Problem entsprechen.

Beachten Sie, dass die spärliche Ramsey-theoretische Sprache von Bill Gasarch in die Kategorie der Sprachen zu fallen scheint, die durch die Sparsamkeit einer harten Sprache konstruiert werden. Wenn man die Instanz als Dreifachzahl anstelle von zwei unären und einer binären codiert, hat die Färbung keine polynomielle Größe mehr, sodass die Sprache nicht offensichtlich in NP ist.

András Salamon
quelle

Dies ist eher ein Kommentar als Antwort auf die überarbeitete Frage (Revision 3) als eine Antwort, aber es ist zu lang für einen Kommentar.

Nur spärliche Sprachen auszuschließen, reicht nicht aus, um Sprachen wie { x ∈ {0,1} ^* : | auszuschließen x | ∈ S } anstelle von {1 ⁿ : n ∈ S }, wobei S eine unendliche Teilmenge von {0, 1, 2,…} ist. Ich möchte darauf hinweisen, dass es schwierig sein kann, zwischen dem Fall zu unterscheiden, in dem eine Sprache zu P / poly gehört, weil sie „im Wesentlichen spärlich“ ist (z. B. {1 ⁿ : n ∈ S } und { x : | x | ∈) S}) und der Fall, dass eine Sprache aus anderen Gründen zu P / poly gehört. Das Problem dabei ist natürlich, wie man den Begriff „im Wesentlichen spärlich“ definiert.

Möglicherweise möchten Sie "essentielle Spärlichkeit" folgendermaßen definieren: Eine Sprache ist im Wesentlichen spärlich, wenn sie auf eine spärliche Sprache reduziert werden kann. Es ist jedoch Vorsicht geboten, da bei Verwendung der Polynomzeit-Turing-Reduzierbarkeit in dieser Definition die Definition der Zugehörigkeit zu P / poly entspricht!

Es ist daher naheliegend, die Viel-Eins-Reduzierbarkeit für das Polynom zu verwenden. Ich weiß nicht, ob dies der Zugehörigkeit zu P / poly entspricht, geschweige denn, ob P / poly eine natürliche Sprache enthält, die in diesem Sinne nicht wesentlich spärlicher ist.

Tsuyoshi Ito
quelle

Eigentlich habe ich darüber nachgedacht, als ich die Antworten gesehen habe, bevor ich die Frage geändert habe, da es natürlich war, an eine boolesche Kombination von spärlichen Sprachen zu denken. Ich dachte , dass mit Ausnahme von Sprachen, die reduzierbar auf spärliche Sprachen (oder vielleicht ein bisschen mehr) sollen genug für meine Frage, aber es scheint , dass dies mehr beteiligt ist , als ich dachte.

A C^{0}

$AC^0$

Kaveh

@Kaveh: Das könnte eine weitere gute Definition für "im Wesentlichen spärlich" sein. Wenn ich Ihren Kommentar lese, frage ich mich, ob P / poly = P∪ (AC0 / poly) (Ich denke nicht), weil irgendein Problem in (P / poly) ∖ ( Man könnte wohl sagen, dass P∪ (AC0 / poly) “berechenbar ist, indem man eine ungleichmäßige Familie von Schaltkreisen polynomialer Größe verwendet, indem man die Leistung von Schaltkreisen polynomialer Größe und die Leistung der Ungleichmäßigkeit wirklich kombiniert”

Tsuyoshi Ito,

Ein mögliches Problem bei meiner Definition anhand eines Ihrer Beispiele ist, ob die folgende Sprache im Wesentlichen spärlich ist : Überprüfen Sie, ob die Anzahl der Einsen in der Eingabe in einer spärlichen Sprache . (Im Allgemeinen sei ein vollständiges Funktionsproblem für die Komplexitätsklasse und sei eine spärliche Sprache. Stellen Sie sich mit einem großen Bereich vor, der der NumOnes-Funktion ähnlich ist. Sei die Menge von s st )

S

$S$

f

$f$

C

$C$

S

$S$

f

$f$

L

$L$

x

$x$

f (x) \in S

$f(x) \in S$

Kaveh

[Fortsetzung] Eine weitere Klasse von Sprachen: Nehmen Sie eine spärliche Sprache und eine Sprache die für die Komplexitätsklasse vollständig ist, und betrachten Sie dann die Verkettung ( ist wobei jedes Symbol durch zwei Kopien davon ersetzt wird zB 010 wird zu 001100). Es kann auch erforderlich sein, dass die Länge des zweiten Teils in der Verkettung geringer ist als die Länge des ersten Teils. Diese Sprachen erfüllen alle Bedingungen, außer dass es sich um ein natürliches Problem handelt, an dessen Lösung die Menschen wirklich interessiert sind.

S

$S$

A

$A$

C

$C$

L = A^{'} .01 . S^{'}

$L=A'.01.S'$

A^{'}

$A'$

A

$A$

Kaveh

@ Kaveh: Hmm, ich verstehe. Vielen Dank für das Teilen der Beispiele. Ich ziehe die Idee zurück, (P / poly) ∖ (P∪ (AC0 / poly)) aus nichttrivialen Gründen als „P / poly“ zu betrachten Da es sich um eine spärliche Sprache handelt, besteht immer noch die Hoffnung, dass die in der Antwort vorgeschlagene Definition von „essentieller Spärlichkeit“ geeignet sein könnte.

Tsuyoshi Ito