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

10

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 .RML(R)1n(x,w)R|x|=nxxSn

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 ).PNP

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 BN P B , i generatory niewrażliwe nie istnieją w stosunku do B.BPBNPB

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 nQBFKKnin1,n2,n1=2ni , dlai>1; jeślixKi | x | =n, a następniexma złożoność Kołmogorowan.ni1i>1xK|x|=nxn

Stany papieru, które w stosunku do , ustala się, że PN P . Możesz wytłumaczyć? (Proszę również wyjaśnić, czy B jest rekurencyjne).B=QBFKPNPB

MS Dousti
źródło

Odpowiedzi:

7

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ż.KKxKnxK(x)=nK(n)lognB

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 (UKU[f(n),g(n)]xd|d|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|)PNP

tow3(1)=2tow3(n+1)=222nCC{1tow3(n):n1}CTIME[nlogn]Ptow3(n)K[logn,nlogn]K[logn,nloglogn]K1tow3(n)CC={1n:(x)[|x|=n and xK]}CNPK

CPKPKNPKCPKMC=L(MK)CPCx=1tow3(n0)

  1. K|x|logloglog|x|U(d)d|x|

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

yKMK yyyK[logn,nk]nkMy K[logn,nloglogn]

Joshua Grochow
źródło
Bardzo szczegółowe i dobrze napisane. Dzięki Joshua!
MS Dousti