Derandomizacja Valiant-Vazirani?

29

Twierdzenie Valiant-Vazirani mówi, że jeśli istnieje wielomianowy algorytm czasu (deterministyczny lub losowy) do rozróżniania między formułą SAT, która ma dokładnie jedno zadowalające przypisanie, a formułą niezadowalającą - wówczas NP = RP . Twierdzenie to zostało udowodnione poprzez wykazanie, że UNIQUE-SAT jest NP- twardy przy randomizowanych redukcjach.

Z zastrzeżeniem prawdopodobnych przypuszczeń o derandomizacji, twierdzenie to można wzmocnić do „skutecznego rozwiązania UNIQUE-SAT implikuje NP = P ”.

Moim pierwszym instynktem było pomyśleć, że sugeruje istnienie deterministycznej redukcji z 3SAT do UNIQUE-SAT, ale nie jest dla mnie jasne, jak tę konkretną redukcję można zdenormalizować.

Moje pytanie brzmi: co uważa się lub wiadomo na temat „derandomizujących redukcji”? Czy to / powinno być możliwe? Co w przypadku VV?

Ponieważ UNIQUE-SAT jest gotowy dla PromiseNP z losowymi redukcjami, czy możemy użyć narzędzia do derandomizacji, aby pokazać, że „deterministyczne rozwiązanie wielomianu czasowego dla UNIQUE-SAT oznacza, że PromiseNP = PromiseP ?

cc.complexity-theory reductions derandomization unique-solution Henry Yuen
źródło

4

W ostatnim akapicie PromiseP = PromiseNP jest równoważne P = NP.

Tsuyoshi Ito

31

Przy prawidłowych założeniach derandomizacji (patrz Klivans-van Melkebeek ) otrzymujesz następujące informacje: Istnieje obliczalny czas polytime st dla wszystkich , $f(\phi)=(\psi_1,\ldots,\psi_k)$ $\phi$

Jeśli jest zadowalające, to co najmniej jedno z ma dokładnie jedno zadowalające przypisanie. $\phi$ $\psi_i$
Jeśli nie jest zadowalająca, wszystkie są niezadowalające. $\phi$ $\psi_i$

Potrzebujesz k wielomianu o długości wtedy . Prawdopodobnie nie można tego zrobić dla . $\phi$ $k=1$

Lance Fortnow
źródło

@LanceFortnow nie

oznaczać Vazirani-Bitny izolacji lemat można derandomized a zatem

oznacza, deterministyczne redukcji do

, która daje

?

P = B P P

$P=BPP$

P = B P P

$P=BPP$

S A T

$SAT$

P = N P

$P=NP$

T ....

1

Nie. Potrzebujesz silniejszego założenia niż P = BPP, aby zdemoralizować Valiant-Vazirani (ponownie odsyłam do Klivans-van Melkebeek). Nawet jeśli dokonujesz derandomizacji Valiant-Vaizarni, daje to tylko wynik, o którym wspomniałem powyżej - nie dostaniesz P = NP, chyba że masz algorytm, który mógłby rozwiązać zadowalanie unikalnych świadków.

Lance Fortnow

@LanceFortnow Tylko dla jasności. Czy możemy uzyskać

po prostu

czy też jest konieczne, aby (przy obecnym stanie wiedzy) prawdopodobne było, że musimy uzyskać derandomizację VV, aby dostać się do

(jest to nieco inne zapytanie niż pytanie, czy tylko P = BPP daje deterministyczną redukcję SAT, ponieważ może nie być konieczne, aby VV w ogóle było potrzebne, aby uzyskać NP w BPP ^ {oplus P }).

P^{\oplus P} = B P P^{\oplus P}

$P^{\oplus P}=BPP^{\oplus P}$

P = B P P

$P=BPP$

P^{\oplus P} = B P P^{\oplus P}

$P^{\oplus P}=BPP^{\oplus P}$

T ....

22

Dla porównania natknąłem się dziś na ten naprawdę interesujący artykuł, który dowodzi, że deterministyczne zmniejszenie jest mało prawdopodobne:

Dell, H., Kabanets, V., Watanabe, O., i van Melkebeek, D. (2012). Czy lemię izolacji Valiant-Vazirani można poprawić? ECCC TR11-151

Twierdzą, że nie jest to możliwe, chyba że NP jest zawarte w P / poli.

Henry Yuen
źródło

Derandomizacja Valiant-Vazirani?

Odpowiedzi: