Ist der Verschluss von P unter e-freien Homomorphismen gleich NP?

Die kontextfreien Sprachen können als Abschluss der Dyck-Sprache unter den Kegeloperationen erhalten werden . Die Dyck-Sprache ist eine deterministische kontextfreie Sprache, und die Kegeloperationen entsprechen den Operationen, die von nichtdeterministischen Finite-State-Wandlern implementiert werden können. Dieses Ergebnis wird weniger überraschend, wenn man bedenkt , dass nicht deterministische transduktor liefern können Zertifikate (oder Gutachtern oder Zeuge Saiten, ich diese Orakel Saiten zunächst fälschlicherweise genannt) der Länge , wobei die Länge des Eingabestrings.$D_2$$O(n)$$n$

Die Definition der Klasse erlaubt Zertifikate der Länge , aber viele -vollständige Probleme sind mit Zertifikaten der Länge vollkommen zufrieden . Der Wandler sollte die Länge des Eingangs nicht unkontrolliert ändern, daher benötigen wir zuverlässige Kegeloperationen. Für sollte dies dem Schließen unter e-freien Homomorphismen entsprechen . (Intuitiv entfernt der Homomorphismus das Zertifikat). Daher meine Frage:$\mathsf{NP}$$O(n^c)$$\mathsf{NP}$$O(n)$$\mathsf P$

Ist der Abschluss von unter e-freien Homomorphismen gleich ?$\mathsf P$$\mathsf{NP}$

Wie oben erwähnt, sollte diese Frage der Frage entsprechen, ob Zertifikate der Länge (anstelle von ) für ausreichen .$O(n)$$O(n^c)$$\mathsf{NP}$

Wie Ryan Williams auf CSTheory.SE erklärt, lautet die Antwort wahrscheinlich nein: Zertifikate mit linearer Größe reichen NP wahrscheinlich nicht aus; Einige NP-Probleme scheinen Zertifikate mit superlinearer Größe zu erfordern.

Sie können auch einige Beispiele für NP-Probleme finden, für die anscheinend superlineare Zertifikate in CSTheory erforderlich sind: Siehe Natürliche NP-vollständige Probleme mit „großen“ Zeugen und Ist die Zeugengröße der Mitgliedschaft für jede NP-Sprache bereits bekannt? . Auch Problem in 2o (n) bei Eingängen mit n Bits unlösbar, unter der Annahme der ETH? könnte auch relevant sein.