Dokonuj wielokrotnych redukcji, a redukcje Turinga określają NPC tej samej klasy

11

Zastanawiam się, czy klasy NPC zdefiniowane przez redukcje wielokrotne i redukcje Turinga są równe.

Edycja: Kolejne pytanie, czy redukcje Turinga powodują tylko załamanie klas C i co-C dla niektórych C lub czy istnieje klasa taka jak istnieje problem, który nie występuje w przy redukcji Karp i która występuje w pod redukcją Turinga ?C ∪ c o - C Cdodo∪doo-dodo

cc.complexity-theory np-hardness reductions Ludovic Patey
źródło
4
Czy czytałeś en.wikipedia.org/wiki/… ?
Jukka Suomela
Dziękuję za twój link. Odpowiada na pierwszą część mojego pytania, ale nie odpowiada, czy istnieją problemy, które nie występują w co-C przy redukcji wielokrotnej jeden i są w C w ramach redukcji Turinga, dla dowolnego C.
Ludovic Patey
1
Przepraszam, może to wydawać się elementarne pytanie, a może nie myślę o tej późnej porze, ale brakuje mi czegoś w artykule na wiki. Artykuł mówi, że w części Redukcje Cooka NP-zupełne jest równe co-NP-zupełne, ale nie widzę tego. NP-hard jest równy co-NP-hard wrt Redukcje Cooka, ale NP-zupełny oznacza zarówno NP-twardy ORAZ NP , i nie rozumiem, dlaczego (np.) TAUT byłby w NP? Tj. TAUT jest co-NP trudny w ramach redukcji Cooka, ale to nie wystarczy, aby być NP-zupełnym.
Kaveh
@Monoid, powinieneś przeredagować swoje pytanie, aby odzwierciedlić to wyjaśnienie. W związku z tym pytanie jest dwuznaczne
Suresh Venkat
możliwy duplikat wielu redukcji w porównaniu z redukcjami Turinga w celu zdefiniowania NPC
Suresh Venkat

Odpowiedzi:

7

Spójrz na to pytanie, a zwłaszcza na tę odpowiedź Aarona Sterlinga. W skrócie: „przypuszcza się, że są odrębnymi pojęciami”.

Matthias
źródło
Wiem, że jeśli NP! = Co-NP, to są one odrębnymi pojęciami, ponieważ redukcja Turinga je załamuje, ale czy mogą istnieć różnice, które nie byłyby załamaniem, na przykład problem w NPI przy redukcji wielokrotnej i w NPC pod redukcją Turinga ?
Ludovic Patey
@ Monoïd: NP ≠ coNP nie oznacza (przynajmniej w oczywisty sposób), że dwa pojęcia redukcji są odrębne. Obawiam się, że mylicie klasę NP (która jest definiowana niezależnie od wyboru pojęcia redukcji) z klasą problemów decyzyjnych redukowanych do NP (która zależy od wyboru pojęcia redukcji).
Tsuyoshi Ito
Ups, mój poprzedni komentarz był błędny. Jeśli NP ≠ coNP, dwa pojęcia redukcji są oczywiście odrębne (SAT jest bezwarunkowo Turingem redukowalnym do UNSAT, ale SAT jest wielokrotnością redukowalną do UNSAT wtedy i tylko wtedy, gdy NP = coNP).
Tsuyoshi Ito
10

„Boolean Hierarchia” BP jest cała hierarchia kombinacji problemów NP ramach redukcji Karp znajdujące się w P ^ NP.

Noam
źródło
9

O ile mi wiadomo, to pytanie naprawdę składa się z dwóch odrębnych pytań, z których pierwsze pojawia się w tytule, a drugie po edycji.

(1) Czy redukcje wielokrotne jeden i redukcje Turinga definiują ten sam zestaw problemów NP-zupełnych (tj. Problemów, które są zarówno w NP, i do których SAT można zredukować)? To, czy NPC w ramach redukcji Turinga jest taki sam, jak NPC w ramach redukcji wielokrotnych jeden, był nadal otwartym problemem siedem lat temu i nie sądzę, że został zamknięty. Szczegółowe informacje można znaleźć w ankiecie z wiadomości ACM SIGACT z czerwca 2003 r.

(2) Do jakiej klasy problemów SAT ma redukcję Turinga i odwrotnie? Jest to klasa problemów trudnych NP (w ramach redukcji Turinga), które występują w P NP . Aby uzyskać więcej informacji na ten temat, zobacz odpowiedź Noama.

Peter Shor
źródło
link nie działa.
T ....
8

To nie odpowiada na twoje pytanie, ale można zadać to samo pytanie w przypadku słabszych obniżek. Na przykład, czy zestaw problemów NP-zupełnych zmienia się, jeśli zezwalamy tylko na redukcje miejsca w dzienniku lub tylko na redukcje AC 0 , a nawet redukcje NC 0 . Zaskakującym faktem jest to, że wszystkie znane problemy z kompletnym NP są kompletne, nawet przy redukcji NC 0 .

Odnośnik: Agrawal, M., Allender, E. i Rudich, S. 1997 Redukcje złożoności obwodu: twierdzenie o izomorfizmie i twierdzenie o luce.

Robin Kothari
źródło
Czy to pytanie o słabsze obniżki jest nadal otwarte? Jeśli mam problem, który był NP całkowity w ramach redukcji P / poli lub BPP, ale najwyraźniej nie w ramach redukcji P bez przyjęcia niepotwierdzonych teoretycznych założeń, czy warto to zanotować?
Peter Shor
@ Peter: W artykule, który zacytowałem, pozostaje otwarty, jeśli istnieje jakiś problem, który jest NP-zupełny przy wielomianowych redukcjach czasu, który nie jest NP-zupełny przy redukcjach AC ^ 0. Odpowiedzi na to pytanie ograniczono złożoności redukcji . Pokazują problem, który jest NP-zupełny z redukcjami ACC, ale nie redukcjami AC ^ 0. Żaden z tych artykułów nie wydaje się komentować problemów, które są NP-zupełne przy redukcjach silniejszych niż czas wielomianowy, i jak to odnosi się do możliwości bycia NP-kompletnym przy redukcjach czasowych.
Robin Kothari,
1

Ten dokument twierdzi, że pokazuje, że istnienie problemu TF N EEXP, który
[wystarczająco trudny do rozwiązania przy zerowym błędzie w najgorszym przypadku] implikuje istnienie
„pełnego języka Turinga dla NP, który nie jest kompletny z tabelą prawdy dla NP. „

Z drugiej strony, nie próbowałem czytać żadnego z ich twierdzonych dowodów na ten wynik,
ale Propozycja 2 i / lub jej dowody pokazują nieporozumienia z definicją ZPP :
Wygląda na to, że faktycznie potrzebują „ FP może rozwiązać wszystkie F ZPP ”, a nie tylko„ ZPP = P ”.


źródło