Kann die Beschränkung auf harte Sprachen einfach sein?

Kann das folgende alles gleichzeitig halten?

1. $L_s$ ist in für alle positiven ganzen Zahlen .$L_{s+1}$$s$
2. $L = \bigcup_s L_s$ 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 .$C$$C$$s$$L_s$$C$

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 .$L$$L_0 = L$$L_{s+1} = L_s \cup \{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 .$L_s$$L$$s$$L_s$$L$$s$

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).$L_{s+1}$$L_s$$L = \cap_s L_s$$L_s$$L_0$

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$L_s$$L_{s+1}$$D_n = \{ x \in \{0,1\}^* : 1x \text{ is the binary expansion of an integer divisible by } n\}$$L_0 = L$ sollte den Trick machen.$L_{s+1} = L_s \cup D_s$

(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 .)$s$$L$$\cup D_s$

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.$\varphi_1, \varphi_2,...$$L_s = SAT \cup \{ \varphi_{i_1},...,\varphi_{i_s}\}$$\varphi_{i_1},...,\varphi_{i_s}$$s$

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 .$L_s$$NP$$\varphi$$x_i$ $\varphi \lor x_1 \lor ... \lor x_n$$i_s$