Kompletność przy iniekcyjnym obniżeniu Karp


12

Redukcja karp jest wielomianową obliczalną w czasie wielokrotnością redukcji między dwoma problemami obliczeniowymi. Wiele redukcji Karp jest w rzeczywistości funkcjami jeden-jeden. Rodzi to pytanie, czy każda redukcja Karp jest iniekcyjna (funkcja jeden do jednego).

Czy istnieje naturalny problem z całkowitym którym wiadomo, że jest całkowity tylko przy zmniejszeniu Karp o wiele jeden, a nie jest znany jako całkowity po wstrzyknięciu zmniejszającym Karp? Co zyskujemy (i tracimy), jeśli zdefiniujemy kompletność za pomocą iniekcyjnej redukcji Karp?NPNP

Jednym oczywistym zyskiem jest to, że rzadkie zestawy nie mogą być kompletne przy iniekcyjnych redukcjach Karp.


Dlaczego Karp zastosował wielomianowe redukcje czasu wielomianowe zamiast redukcji jeden-jeden? Czy wpłynęły na niego ograniczenia zastosowane w teorii obliczalności?
Mohammad Al-Turkistany,

1
Myślę, że już odpowiedziałem na to (lub bardzo blisko powiązane) pytanie w komentarzu do tej odpowiedzi: cstheory.stackexchange.com/a/172/129 .
Joshua Grochow

@JoshuaGrochow Injectivity daje nam dolną granicę gęstości zestawów twardych. Czy zdajesz sobie sprawę z problemu NP-zupełnego, o którym wiadomo, że nie jest kompletny w przypadku iniekcji Karp? Rozważ opublikowanie komentarza jako odpowiedzi.
Mohammad Al-Turkistany

Odpowiedzi:


7

Oto odpowiedź na szczególny przypadek, w którym ograniczamy się do przypadku, w którym redukcję Karp można również zwiększyć , wraz z wprowadzaniem go. (Zwiększanie długości oznacza, że , gdzie jest funkcją reprezentującą redukcję).fa|f(x)|>|x|f

Twierdzenie: Jeśli każda redukcja Karp w może zostać przekształcona w iniekcyjną i zwiększającą długość, wówczas zachowuje.P N PNPPNP

Dowód. Załóżmy, że każda redukcja Karp w może zostać przekształcona w iniekcyjną i zwiększającą długość. Istnieją dwie możliwości:NP

  1. Wszystkie te redukcje są nie tylko obliczalne w czasie wielomianowym, ale odwrotność każdej funkcji, która istnieje po uczynieniu funkcji iniekcyjnej, jest również obliczalna w czasie wielomianowym. Wiadomo, że jeśli oba języki są redukowalne względem siebie poprzez redukcje, które są obliczalne w czasie polime, są odwracalne i zwiększają się w długości, to są one polimorficzne izomorficzne (patrz Twierdzenie 7.4 w książce „Teoria złożoności obliczeniowej” Ding-Zhu Du i Ker-I Ko). Oznaczałoby to, że wszystkie kompletne języki są izomorficzne, to znaczy utrzymuje się hipoteza izomorfizmu, o której wiadomo, że implikuje .p P N PNPpPNP

  2. Istnieje co najmniej jedna z tych funkcji, dla których odwrotności nie da się obliczyć w czasie wielomianowym. Ta funkcja stanowiłaby przykład funkcji jednokierunkowej w najgorszym przypadku. Wiadomo jednak, że istnienie funkcji jednokierunkowych w najgorszym przypadku oznacza również . (Zobacz Twierdzenie 2.5 w książce „Towarzysz teorii teorii złożoności” Hemaspaandry i Ogihary.)PNP

Dlatego założenie, że każda redukcja Karp może być iniekcyjna i zwiększanie długości implikuje , więc prawdopodobnie bardzo trudno to udowodnić. Z drugiej strony może być łatwiej obalić, ponieważ nie wydaje się to mieć tak dramatycznych konsekwencji. Nie jest również jasne, co się stanie, jeśli odrzucimy założenie dotyczące zwiększania długości.PNP


2
Odwrotnością funkcji zwiększania długości jest zmniejszanie długości . A może coś mi brakuje?
Emil Jeřábek

1
Czy p-izomorfizm problemów NP-zupełnych implikuje P! = NP z trywialnego powodu, że język jednoelementowy nie jest izomorficzny w stosunku do języka dwuelementowego, czy też jest bardziej wyrafinowany? Jeśli zezwolisz na języki skończone, roszczenie ma prosty bezpośredni dowód i wymaga tylko iniekcji: mianowicie, język jednoelementowy jest NP-kompletny przy wielu redukcjach jeden, jeśli P = NP, ale nie może być NP-kompletny pod jednym -jedna redukcja.
Emil Jeřábek

1
Dlaczego zamiast tego powinniśmy nalegać na redukcje iniekcji? Zastrzyki nie wydają się być w żaden sposób związane z celem redukcji, więc naturalnym wyborem jest nie wymagać tego. Istnieje wiele innych arbitralnych ograniczeń, które można nałożyć, ale jaki byłby sens?
Emil Jeřábek

1
Dlaczego zbiory skończone nie powinny być NP-kompletne, gdy P = NP? Zauważ, że w tej sytuacji inne głupie zbiory są kompletne NP nawet przy redukcjach jeden-jeden, takich jak zbiór wszystkich nieparzystych liczb binarnych.
Emil Jeřábek

2
@JoshuaGrochow Nie musimy uzyskiwać redukcji inv, li z odwrotności, aby zająć się odwrotną kuracją. Jeśli weźmiemy dwa języki kompletne NP, oba mają redukcję Karp do drugiego (ale te redukcje na ogół nie są odwrotnością). Jeśli teraz założymy, że można dokonać dowolnej redukcji Karp, inv, li, wówczas uzyskamy redukcję inv, li w obu kierunkach, więc dzięki przytoczonemu twierdzeniu można je przekształcić w p-izomorfizm.
Andras Farago,

7

Nie, żaden taki naturalny problem nie jest znany. Powodem jest to, że o ile mi wiadomo, wszystkie problemy naturalne są znane jako p-izomorficzne w stosunku do SATNP , a twierdzenie Cooka-Levina faktycznie pokazuje, że SAT jest kompletny dla w ramach redukcji jeden do jednego. Połączenie redukcji jeden do jednego z SAT z p-izomorfizmem daje jeden do jednego zmniejszenie dowolnego problemu z p-izomorficznym.NP

W rzeczywistości nawet potencjalne „nienaturalne” kontrprzykłady do hipotezy izomorfizmu - k-twórcze zestawy Twierdzenia Josepha i Younga 2.2 - są kompletne przy jednorazowych redukcjach konstrukcyjnych.

[Powtórzono z mojego komentarza tutaj :] Ponieważ większość budowanych przez nas redukcji wielokrotnych to tak naprawdę redukcje jeden-jeden, dlaczego nie badamy tych, kiedy są one formalnie silniejsze i i tak dostajemy je przez większość czasu? Myślę, że ponieważ łatwiej jest nie zadawać sobie trudu wykazania iniekcji, mimo że zwykle go mamy. W tym sensie być może redukcje „jeden do jednego” to „redukcje Złotowłosa:” odpowiednia moc, właściwa prostota dowodu.


Czy istnieje intuicyjne wyjaśnienie kreatywności zestawu?
Mohammad Al-Turkistany

Dziękuję za odpowiedź. Chciałbym móc przyjąć dwie odpowiedzi.
Mohammad Al-Turkistany

1

W rzeczywistości redukcje iniekcyjne są przydatne w kryptografii. Załóżmy, że masz system dowodu ZK dla relacji NP R nad językiem L. Jeśli chcesz zbudować dowód ZK dla innej relacji NP R 'w języku L', musisz znaleźć dwie funkcje f i g o następujących właściwościach : 1. x należy do L 'iff f (x) należy do L, 2. Jeśli (x, w) należy do R', to (f (x), g (x, w)) należy do R. 3. Ponadto , f i g muszą być wydajnie obliczalne.

Powyższe właściwości sugerują, że jeśli system dowodu dla R jest kompletny i zdrowy, to system dowodu dla R '(zdefiniowany w oczywisty sposób za pomocą powyższych funkcji w celu zmniejszenia wystąpień relacji do drugiego) jest kompletny i również poprawny.

Co powiesz na udowodnienie, że nowy system jest również ZK lub nie do odróżnienia przez świadka (WI)? Jeśli f jest odwracalny, możesz udowodnić, że tak uzyskanym systemem dowodowym jest ZK. W przeciwnym razie, aby udowodnić, że musisz założyć, że układem sprawdzającym dla R jest wejście pomocnicze ZK (a nie tylko ZK). W przypadku WI, jeżeli f jest odwracalny, można udowodnić, że systemem dowodowym dla R 'jest WI. Bez faktu, że f jest odwracalny, nie jestem pewien, czy możesz to udowodnić

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.