¿Puede ser fácil limitar los idiomas difíciles?

¿Puede todo lo siguiente sostenerse simultáneamente?

1. $L_s$ está contenido en para todos los enteros positivos .$L_{s+1}$$s$
2. $L = \bigcup_s L_s$ es el lenguaje de todas las palabras finitas sobre .$\{0,1\}$
3. Hay una cierta clase de complejidad y una noción de reducción adecuada de tal que para cada uno , L_s es difícil para C .$C$$C$$s$$L_s$$C$

Creo que podemos comenzar con un lenguaje base , luego tomar L 0 = L y L s + 1 = L s ∪ { 0 , 1 } s + 1 .$L$$L_0 = L$$L_{s+1} = L_s \cup \{0,1\}^{s+1}$

Es decir, cada es la unión de L con todas las cadenas de longitud hasta s . Cada L s es al menos tan difícil como L pero no es más difícil (en un sentido asintótico), suponiendo que podamos contar hasta s .$L_s$$L$$s$$L_s$$L$$s$

También pensé en el "límite" opuesto, por lo que cada está contenido en L s , y L = ∩ s L s es fácil mientras que cada L s es difícil. Pero creo que podríamos comenzar con un lenguaje difícil (pero contable) L 0 y simplemente eliminar una palabra en cada paso; la intersección debe estar vacía (cada palabra se elimina eventualmente).$L_{s+1}$$L_s$$L = \cap_s L_s$$L_s$$L_0$

Sólo para añadir a las respuestas de Marzio y usul de: el mismo se puede hacer incluso si uno quiere exigir que la diferencia entre y L s + 1 sea un conjunto infinito (que es una manera de tratar de hacer la pregunta menos trivialmente respondió: pero, como vemos, no funciona). Sea D n = { x ∈ { 0 , 1 } ∗ : 1 x  es la expansión binaria de un entero divisible por  n } . Luego tomando L 0 = L y 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$ debería hacer el truco.$L_{s+1} = L_s \cup D_s$

(Para cualquier fijo , si L era, por ejemplo, CLIQUE, debería ser relativamente fácil tomar una reducción de SAT a CLIQUE y modificarlo por algo como relleno, de modo que todavía sea una reducción de SAT a CLIQUE ∪ D s .)$s$$L$$\cup D_s$

Dada una enumeración de binarios fórmulas booleanas codificados definen L s = S A T ∪ { φ i 1 , . . . , Φ i s } donde φ i 1 , . . . , Φ i s son los primeros s fórmulas unsatisfiable en la enumeración.$\varphi_1, \varphi_2,...$$L_s = SAT \cup \{ \varphi_{i_1},...,\varphi_{i_s}\}$$\varphi_{i_1},...,\varphi_{i_s}$$s$

es claramente difícil para N P : dada una fórmula booleana φ agregue suficientes nuevas variables OR-ed x i φ ∨ x 1 ∨ . . . ∨ x n hasta que su índice en la enumeración sea mayor que (constante) i s .$L_s$$NP$$\varphi$$x_i$ $\varphi \lor x_1 \lor ... \lor x_n$$i_s$