Bisakah batas bahasa sulit menjadi mudah?

Apakah semua berikut ini dapat bertahan secara bersamaan?

1. $L_s$ terkandung dalam untuk semua bilangan bulat positif .$L_{s+1}$$s$
2. $L = \bigcup_s L_s$ adalah bahasa dari semua kata hingga lebih dari .$\{0,1\}$
3. Ada beberapa kelas kompleksitas $C$ dan gagasan yang tepat pengurangan untuk $C$ sehingga untuk setiap $s$ , $L_s$ sulit untuk $C$ .

Saya pikir kita bisa mulai dengan beberapa bahasa dasar , lalu ambil dan .$L$$L_0 = L$$L_{s+1} = L_s \cup \{0,1\}^{s+1}$

Artinya, masing-masing adalah penyatuan dengan semua string panjang hingga . Setiap setidaknya sekeras tetapi tidak lebih sulit (dalam arti asimptotik), dengan asumsi kita dapat menghitung .$L_s$$L$$s$$L_s$$L$$s$

Saya juga memikirkan kebalikan "limit", sehingga setiap terkandung dalam , dan mudah sedangkan setiap$L_{s+1}$$L_s$$L = \cap_s L_s$ sulit. Tapi saya pikir kita bisa mulai dengan bahasa L 0 yang sulit (tapi bisa dihitung)dan hanya menghapus satu kata pada setiap langkah; persimpangan harus kosong (setiap kata pada akhirnya dihapus).$L_s$$L_0$

Hanya untuk menambah jawaban Marzio dan ushul ini: yang sama dapat dilakukan bahkan jika seseorang ingin mengharuskan perbedaan antara dan L s + 1 menjadi himpunan tak terhingga (yang merupakan salah satu cara untuk mencoba untuk membuat pertanyaan yang kurang sepele menjawab, tetapi, seperti yang kita lihat, tidak berhasil). Misalkan D n = { x ∈ { 0 , 1 } ∗ : 1 x  adalah ekspansi biner dari sebuah integer yang dapat dibagi oleh  n } . Kemudian mengambil L 0 = L dan 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$ harus melakukan trik.$L_{s+1} = L_s \cup D_s$

(Untuk setiap tetap , jika L adalah, katakanlah, CLIQUE, itu harus relatif mudah untuk mengambil pengurangan dari SAT untuk CLIQUE dan memodifikasinya dengan sesuatu seperti melakukan padding sehingga masih pengurangan dari SAT ke CLIQUE ∪ D s .)$s$$L$$\cup D_s$

Mengingat pencacahan biner formula boolean encoded mendefinisikan L s = S A T ∪ { φ i 1 , . . . , Φ i s } di mana φ i 1 , . . . , Φ i s adalah yang pertama s formula unsatisfiable di pencacahan.$\varphi_1, \varphi_2,...$$L_s = SAT \cup \{ \varphi_{i_1},...,\varphi_{i_s}\}$$\varphi_{i_1},...,\varphi_{i_s}$$s$

jelas sulit bagi N P : diberikan formula boolean φ menambahkan untuk itu cukup baru variabel OR-ed x i φ ∨ x 1 ∨ . . . ∨ x n hingga indeksnya dalam enumerasi menjadi lebih besar dari (konstan) i s .$L_s$$NP$$\varphi$$x_i$ $\varphi \lor x_1 \lor ... \lor x_n$$i_s$