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 \cup co-C$ $C$

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

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 ⁰ , a nawet redukcje NC ⁰ . Zaskakującym faktem jest to, że wszystkie znane problemy z kompletnym NP są kompletne, nawet przy redukcji NC ⁰ .

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,

5

Te dwa pojęcia są różne przy pewnych rozsądnych założeniach. Sprawdź ten artykuł: http://www.cs.iastate.edu/~pavan/papers/reductions.pdf

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 ”.