La limite des langues dures peut-elle être facile?

Les éléments suivants peuvent-ils tous tenir simultanément?

1. $L_s$ est contenu dans$L_{s+1}$ pour tous les entiers positifs$s$ .
2. { 0 , 1 $L = \bigcup_s L_s$ est la langue de tous les mots finis sur .$\{0,1\}$
3. Il y a une classe de complexité et une notion de réduction appropriée pour telle que pour chaque , est difficile pour .C s L s$C$$C$$s$$L_s$$C$

Je pense que nous pouvons simplement commencer avec un langage de base , puis prendre L 0 = L et L s + 1 = L s ∪ { 0 , 1 } s + 1 .$L$$L_0 = L$$L_{s+1} = L_s \cup \{0,1\}^{s+1}$

Autrement dit, chaque est l'union de L avec toutes les chaînes de longueur jusqu'à s . Chaque L s est au moins aussi dur que L mais n'est pas plus difficile (dans un sens asymptotique), en supposant que nous pouvons compter jusqu'à s .$L_s$$L$$s$$L_s$$L$$s$

J'ai aussi pensé à la "limite" opposée, donc chaque est contenu dans L s , et L = ∩ s L s est facile tandis que chaque L s est dur. Mais je pense que nous pourrions simplement commencer avec une langue difficile (mais dénombrable) L 0 et simplement supprimer un mot à chaque étape; l'intersection doit être vide (chaque mot est finalement supprimé).$L_{s+1}$$L_s$$L = \cap_s L_s$$L_s$$L_0$

Juste pour ajouter aux réponses de Marzio et usul: la même chose peut être faite même si l'on veut exiger que la différence entre et L s + 1 soit un ensemble infini (ce qui est une façon d'essayer de rendre la question moins triviale, mais, comme nous le voyons, ne fonctionne pas). Soit D n = { x ∈ { 0 , 1 } ∗ : 1 x  est l'expansion binaire d'un entier divisible par  n } . En prenant alors L 0 = L et 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$ devrait faire l'affaire.$L_{s+1} = L_s \cup D_s$

(Pour tout fixe , si L était, disons, CLIQUE, il devrait être relativement facile de prendre une réduction de SAT en CLIQUE et de la modifier par quelque chose comme le remplissage afin qu'elle soit toujours une réduction de SAT en CLIQUE ∪ D s .)$s$$L$$\cup D_s$

Étant donné une énumération de formules booléennes binaires codées définissent L s = S A T ∪ { φ i 1 , . . . , Φ i s } où φ i 1 , . . . , Φ i s sont les premiers de formules insatisfiables dans l'énumération.$\varphi_1, \varphi_2,...$$L_s = SAT \cup \{ \varphi_{i_1},...,\varphi_{i_s}\}$$\varphi_{i_1},...,\varphi_{i_s}$$s$

est clairement difficile pour N P : étant donné une formule booléenne φ ajoutez-y suffisamment de nouvelles variables OR-ed x i φ ∨ x 1 ∨ . . . ∨ x n jusqu'à ce que son indice dans l'énumération devienne supérieur à (constant) i s .$L_s$$NP$$\varphi$$x_i$ $\varphi \lor x_1 \lor ... \lor x_n$$i_s$