Kann die Beschränkung auf harte Sprachen einfach sein?

13

Kann das folgende alles gleichzeitig halten?

  1. Ls ist in für alle positiven ganzen Zahlen .Ls+1s
  2. L=sLs ist die Sprache aller endlichen Wörter über .{0,1}
  3. Es besteht eine gewisse Komplexitätsklasse und eine Vorstellung der Reduktion geeignet für , so dass für jeden , für schwer ist .CCsLsC
András Salamon
quelle
1
Kann das funktionieren? einer Aufzählung von (binär codierten) Booleschen Formeln definieren Sie wobei sind die ersten unerfüllbar Formeln in der Aufzählung? L s = S A T { φ i 1 , . . . , Φ i s } φ i 1 , . . . , Φ i s sφ1,φ2,...Ls=SAT{φi1,...,φis}φi1,...,φiss
Marzio De Biasi
Das scheint zu funktionieren, vielleicht eine Antwort daraus zu machen?
András Salamon

Antworten:

10

Ich denke, wir können einfach mit einer Basissprache und dann L 0 = L und L s + 1 = L s{ 0 , 1 } s + 1 nehmen .LL0=LLs+1=Ls{0,1}s+1

Das heißt, jedes ist die Vereinigung von L mit allen Strings der Länge bis zu s . Jedes L s ist mindestens so hart wie L, aber nicht härter (im asymptotischen Sinne), vorausgesetzt, wir können bis s zählen .LsLsLsLs

Ich dachte auch über die anderen "Grenze", so dass jeder in enthalten ist L s und L = s L s ist einfach , während jeder L s hart ist. Aber ich denke, wir könnten einfach mit einer harten (aber abzählbaren) Sprache L 0 beginnen und bei jedem Schritt nur ein Wort entfernen. Die Kreuzung sollte leer sein (jedes Wort wird schließlich entfernt).Ls+1LsL=sLsLsL0

usul
quelle
7

Um die Antworten von Marzio und Usul zu ergänzen: Das Gleiche kann getan werden, auch wenn man verlangen möchte, dass der Unterschied zwischen und L s + 1 eine unendliche Menge ist (eine Möglichkeit, die Frage weniger trivial zu beantworten). aber, wie wir sehen, funktioniert nicht). Lassen D n = { x { 0 , 1 } * : 1 x  die binäre Erweiterung einer ganze Zahl ist teilbar durch  n } . Dann gilt L 0 = L und L s + 1 =LsLs+1Dn={x{0,1}:1x is the binary expansion of an integer divisible by n}L0=L sollte den Trick machen.Ls+1=LsDs

(Für alle festen , wenn L war, sagen wir, Clique, sollte es relativ einfach sein , eine Reduktion von SAT nach CLIQUE zu nehmen und ändern Sie es durch so etwas wie so Klotzen , dass es immer noch eine Reduktion von SAT nach CLIQUE ist D s .)sLDs

Joshua Grochow
quelle
4

Gegeben eine Aufzählung von binären codierten Boolesche Formeln definieren L s = S A T { φ i 1 , . . . , Φ i s } wobei φ i 1 , . . . , Φ i s sind die ersten s unerfüllbar Formeln in der Aufzählung.φ1,φ2,...Ls=SAT{φi1,...,φis}φi1,...,φiss

ist eindeutig schwer für N P : Addiere mit einer gegebenen Booleschen Formel φ genug neue OR-ed-Variablen x i φ x 1. . . x n, bis sein Index in der Aufzählung größer als (konstant) i s wird .LsNPφxi φx1...xnis

Marzio De Biasi
quelle
1
Zweitens scheint dies eine Kodierung zu erfordern, für die garantiert jedes endliche Wort als Kodierung einer CNF-Formel erscheint. Man könnte dann jedoch die zweite Bedingung so ändern, dass die Sprache aller syntaktisch gültigen CNF-Formeln in der Codierung ist; das fängt immer noch den Geist der Frage ein. L
András Salamon
Für die Härte scheint es ausreichend zu sein, zu beobachten, dass, wenn NP-hart ist und L ' eine endliche Sprache ist, L L ' auch NP-hart ist. LLLL
András Salamon
@ AndrásSalamon: Du hast Recht mit dem Härtenachweis: -S! Ich denke jedoch, dass eine "perfekte" Codierung (eine Bijektion zwischen N und allen gültigen Formeln) in Polynomzeit möglich und berechenbar ist.
Marzio De Biasi