Światy, w stosunku do których nie istnieją „nietykalne generatory”

Niewrażliwe generatory są zdefiniowane następująco:

Niech będzie relacją NP, a M będzie maszyną, która akceptuje L ( R ) . Nieformalnie program jest niewrażliwym generatorem, jeśli na wejściu 1 n wytwarza pary instancji-świadka ( x , w ) ∈ R , z | x | = n , zgodnie z rozkładem, zgodnie z którym przeciwnik wielomianowy, któremu podano x, nie znajduje świadka, że x ∈ S , z zauważalnym prawdopodobieństwem, dla nieskończenie wielu długości n .$R$$M$$L(R)$$1^n$$(x, w) \in R$$|x| = n$$x$$x \in S$$n$

Niewrażliwe generatory, zdefiniowane po raz pierwszy przez Abadi i in. , znaleziono wiele aplikacji w kryptografii.

Istnienie niewrażliwych generatorów opiera się na założeniu, że , ale może to być niewystarczające (patrz także pokrewny temat ).$\mathbf{P} \neq \mathbf{NP}$

Twierdzenie 3 Abadi i in. cytowany powyżej artykuł pokazuje, że żaden dowód na istnienie niewrażliwych generatorów nie relatywizuje:

Twierdzenie 3. Istnieje wyrocznia taka, że P B ≠ N P B , i generatory niewrażliwe nie istnieją w stosunku do B.$B$$\mathbf{P}^B \neq \mathbf{NP}^B$

Nie rozumiem części dowodu tego twierdzenia. Niech oznacza rozłączną operację związkową . Niech Q B F będzie kompletnym językiem PSPACE o zadowalających ilościowych formułach boolowskich i niech K będzie wyjątkowo rzadkim zestawem ciągów o maksymalnej złożoności Kołmogorowa. W szczególności K zawiera jeden ciąg każdej długości n i , gdzie sekwencja n 1 , n 2 , … jest zdefiniowana przez: n 1 = 2 , n i jest potrójnie wykładniczy w $\sqcup$$QBF$$K$$K$$n_i$$n_1, n_2, \ldots$$n_1 = 2$$n_i$ , dlai>1; jeślix∈Ki | x | =n, a następniexma złożoność Kołmogorowan.$n_{i-1}$$i > 1$$x \in K$$|x| = n$$x$$n$

Stany papieru, które w stosunku do , ustala się, że P ≠ N P . Możesz wytłumaczyć? (Proszę również wyjaśnić, czy B jest rekurencyjne).$B = QBF \sqcup K$$\mathbf{P} \neq \mathbf{NP}$$B$

Gdyby po prostu mówili o złożoności Kołmogorowa (niezwiązanej z zasobami), wówczas byłby nieobliczalny (w przeciwnym razie można użyć maszyny obliczeniowej K, aby podać krótkie opisy ciągów x ∈ K , ponieważ wszystko, co musisz zrobić, to opisać urządzenie i długość n z x , i ma K ( x ) = n a K ( n ) ≤ log n ), stąd B będzie nieobliczalnych również.$K$$K$$x \in K$$n$$x$$K(x) = n$$K(n) \leq \log n$$B$

Jednak praca Abadi i in. odniesienie ( Hartmanis. Uogólniona złożoność Kołmogorowa i struktura wykonalnych obliczeń. FOCS 1983. ) wykorzystuje ograniczoną do zasobów wersję złożoności Kołmogorowa. Niech będzie wydajną uniwersalną maszyną Turinga. Zdefiniuj K U [ f ( n ) , g ( n ) ] jako zbiory ciągów x, tak aby istniał ciąg d długości | d | ≤ f ( | x | ) takie, że x = U $U$$K_U[f(n), g(n)]$$x$$d$$|d| \leq f(|x|)$ a obliczenie U ( d ) zajmuje najwyżej g ( | x | ) czasu. Na górze drugiej kolumny na str. 444 tego papieru Hartmanis opisano sposób używania tego pojęcia skonstruować (obliczeniowy) wyrocznią względem którego P ≠ N P .$x = U(d)$$U(d)$$g(|x|)$$P \neq NP$

$tow_3(1)=2$$tow_3(n+1)=2^{2^{2^{n}}}$$C$$C \subseteq \{1^{tow_3(n)} : n \geq 1\}$$C \in TIME[n^{\log n}] - P$$tow_3(n)$$K[\log n, n^{\log n}] - K[\log n, n^{\log \log n}]$$K$$1^{tow_3(n)} \in C$$C = \{1^n : (\exists x)[|x|=n \text{ and } x \in K]\}$$C \in NP^{K}$

$C \notin P^{K}$$P^K \neq NP^K$$C \in P^{K}$$M$$C = L(M^K)$$C \in P$$C$$x = 1^{tow_3(n_0)}$

1. $K$$|x|$$\log \log \log |x|$$U(d)$$d$$|x|$

2. $M(x)$$M(x)$$|x|$

$y \in K$$M^K$ $y$$y$$y \in K[\log n, n^k]$$n^k$$M$$y$ $K[\log n, n^{\log \log n}]$