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

13

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

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

cc.complexity-theory complexity-classes reductions

— András Salamon
źródło

1

Czy to może zadziałać? Biorąc wyliczenia

kwasu (zakodowanych binarnie) Preparaty boolowskie określić

, gdzie

są pierwszymi

unsatisfiable wzory na wyliczenie?

φ_{1}, φ_{2}, . . .

$\varphi_1, \varphi_2,...$

L_{s} = S A T \cup {φ_{i_{1}}, . . ., φ_{i_{s}}}

$L_s = SAT \cup \{ \varphi_{i_1},...,\varphi_{i_s}\}$

φ_{i_{1}}, . . ., φ_{i_{s}}

$\varphi_{i_1},...,\varphi_{i_s}$

s

$s$

— Marzio De Biasi

To wydaje się działać, może sprawi, że będzie to odpowiedź?

— András Salamon

10

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

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

I również, że o przeciwnym „graniczna”, więc każdy jest zawarta w , a jest łatwe, przy czym każdy jest trudne. Myślę jednak, że moglibyśmy zacząć od twardego (ale policzalnego) języka 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$

— usul
źródło

7

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 jest zbiorem nieskończonym (co jest jednym ze sposobów, aby starać się kwestia mniej trywialnie odpowiedział ale, jak widzimy, nie działa). Niech . Następnie biorąc i $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 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 .) $s$ $L$ $\cup D_s$

— Joshua Grochow
źródło

4

Biorąc wyliczenia dwuskładnikowych zakodowanych wzorów boolowskie określić , gdzie są pierwsze 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$

— Marzio De Biasi
źródło

1

L

$L$

L

$L$

L^{'}

$L'$

L \cup L^{'}

$L \cup L'$

@ AndrásSalamon: masz rację co do twardości: -S! Uważam jednak, że „idealne” kodowanie (bijectcja między N i wszystkimi prawidłowymi formułami) jest możliwe i obliczalne w czasie wielomianowym.

— Marzio De Biasi