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 .
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 ).
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.
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 n , dlai>1; jeślix∈Ki | x | =n, a następniexma złożoność Kołmogorowan.
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).
źródło