Problemy, które są NP-zupełne w przypadku randomizacji lub redukcji P / poli.

W tym pytaniu wydaje się, że zidentyfikowaliśmy naturalny problem, który jest zupełny NP przy redukcjach losowych, ale być może nie przy redukcjach deterministycznych (chociaż zależy to od tego, które niesprawdzone założenia teorii liczb są prawdziwe). Czy znane są inne problemy? Czy istnieją jakieś naturalne problemy, które są NP-zupełne w przypadku redukcji P / poli, ale nie są znane w przypadku redukcji P?

cc.complexity-theory np-hardness big-list randomness reductions Peter Shor
źródło

Unikalny SAT to

N P

$NP$ twardy przy losowej redukcji.

Mohammad Al-Turkistany

Nie rozumiem, dlaczego Unique SAT nie powinien liczyć się jako odpowiedź (nawet jeśli nie tego szukałem). Myślę, że liczy się to jako naturalny problem.

Peter Shor,

Chciałem tylko dodać, że najkrótsza problemem wektor dla LLL pod

normą dla randomizowanych redukcji (papier przez Ajtai tutaj ) jest NP-trudny. O ile wiem, nie jest znany jako NP-Hard przy nielosowych redukcjach, więc nie spełnia twoich kryteriów, ale pomyślałem, że i tak należy o tym wspomnieć.

L_{2}

$L_2$

user834

@Joshua: W niektórych problemach NP-zupełnych związanych z łamigłówkami (takich jak Sudoku) wyjątkowość rozwiązania jest naturalnym założeniem. Wydaje mi się, że dzięki temu SAT z co najwyżej jednym rozwiązaniem (wolę to nazwać jednoznacznym SAT) jest bardziej naturalny, niż mogłoby się początkowo wydawać.

Tsuyoshi Ito

Dlaczego wszyscy piszą odpowiedzi w komentarzach? : P

Hsien-Chih Chang 張顯之

Odpowiedzi:

W przypadku losowej redukcji z prawdopodobieństwem (znany również jako redukcja, w dyskusji na temat losowych redukcji patrz „O wyjątkowej satysfakcji i losowych redukcjach”) $\frac{1}{2}$ $\gamma$

Podzielność liniowa
Binarne kwadratowe równania diofantyczne

są NP-pełne, ale to samo nie jest znane z deterministycznych redukcji (o ile mi wiadomo, nieco przestarzała dyskusja na temat tej sytuacji, patrz tutaj ). redukowalność została wprowadzona w pracy „ Redukcyjność, losowość i trudność ” Leonarda Adlemana i Kennetha Mandersa (tam również zaproponowano dowody na powyższe problemy). $\gamma$

Istnieją inne takie przykłady w „ Katalogu klas złożoności ”, ale nie sprawdziłem, co wiadomo o ich kompletności NP przy deterministycznych redukcjach.

Oleksandr Bondarenko
źródło

Zgodnie z sugestią Piotra przekształciłem swój komentarz w odpowiedź.

Mężnym-Vazirani twierdzenie, że jeśli Unikalne SAT , a następnie . Aby udowodnić swoje twierdzenie, wykazali, że problem z obietnicą Unique SAT to twardy przy losowych redukcjach. $\in P$ $NP=RP$ $NP$

[1] Valiant, Leslie; Vazirani, Vijay. „NP jest tak łatwe, jak wykrywanie unikalnych rozwiązań”, Theoretical Computer Science, 47: 85–93

Mohammad Al-Turkistany
źródło

Zgodnie z sugestią Piotra przekonwertowałem swój komentarz na odpowiedź:

$L_2$ $NP$

użytkownik834
źródło