Czy ograniczenie twardych języków może być łatwe?

Czy następujące elementy mogą być przechowywane jednocześnie?

1. jest zawarte w L s + 1 dla wszystkich dodatnich liczb całkowitych s .$L_s$$L_{s+1}$$s$
2. jest język wszystkich ograniczonych słów nad { 0 , 1 } .$L = \bigcup_s L_s$$\{0,1\}$
3. Istnieje pewna klasa złożoności i pojęcie odpowiedniego obniżenia dla C taki, że dla każdego s , L s jest trudne dla C .$C$$C$$s$$L_s$$C$

Myślę, że możemy zacząć od jakiegoś podstawowego języka , a następnie wziąć L 0 = L i L s + 1 = L s ∪ { 0 , 1 } s + 1 .$L$$L_0 = L$$L_{s+1} = L_s \cup \{0,1\}^{s+1}$

Oznacza to, że każdy jest sumą L ze wszystkich ciągów długości do s . Każdy L s jest co najmniej tak mocno, jak L ale nie jest trudniejsze (w sensie asymptotycznej), zakładając, że możemy liczyć na s .$L_s$$L$$s$$L_s$$L$$s$

I również, że o przeciwnym „graniczna”, więc każdy jest zawarta w L y , a L = ∩ y L e jest łatwe, przy czym każdy L y jest trudne. Myślę jednak, że moglibyśmy zacząć od twardego (ale policzalnego) języka L 0 i po prostu usunąć jedno słowo na każdym kroku; skrzyżowanie powinno być puste (każde słowo zostanie ostatecznie usunięte).$L_{s+1}$$L_s$$L = \cap_s L_s$$L_s$$L_0$

Wystarczy dodać do odpowiedzi Marzio i usul to: to samo można zrobić, nawet jeśli chce się wymagać, że różnica między i L s + 1 jest zbiorem nieskończonym (co jest jednym ze sposobów, aby starać się kwestia mniej trywialnie odpowiedział ale, jak widzimy, nie działa). Niech D n = { x ∈ { 0 , 1 } ∗ : 1 x  jest binarnym rozwinięciem liczby całkowitej podzielnej przez  n } . Następnie biorąc L 0 = L i 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$ powinno wystarczyć.$L_{s+1} = L_s \cup D_s$

(Dla dowolnych ustalonych , jeśli L był, powiedzmy, KLIKNIĘCIEM, powinno być względnie łatwe przejście z SAT na CLIQUE i zmodyfikowanie go za pomocą dopełnienia, aby nadal było redukcją z SAT do KLIQUE ∪ D s .)$s$$L$$\cup D_s$

Biorąc wyliczenia dwuskładnikowych zakodowanych wzorów boolowskie określić L y = S T ∪ { φ ı 1 , . . . , Φ i s } , gdzie φ i 1 , . . . , Φ i y są pierwsze s unsatisfiable wzory na wyliczenie.$\varphi_1, \varphi_2,...$$L_s = SAT \cup \{ \varphi_{i_1},...,\varphi_{i_s}\}$$\varphi_{i_1},...,\varphi_{i_s}$$s$

$L_s$$NP$$\varphi$$x_i$ $\varphi \lor x_1 \lor ... \lor x_n$$i_s$