Czy redukcja karp jest identyczna z redukcją Levina

12

Definicja: Redukcja karp

Język jest karpem redukowalnym do języka jeśli istnieje funkcja obliczalna w czasie wielomianowym tak, że dla każdego , wtedy i tylko wtedy, .ABf:{0,1}{0,1}xxAf(x)B

Definicja: Redukcja Levina

Problem wyszukiwania można sprowadzić do Levina do problemu wyszukiwania jeśli istnieje funkcja czasu wielomianowego której Karp redukuje do a istnieją funkcje obliczeniowe wielomianowe i takie, żeVAVBfL(VA)L(VB)gh

  1. x,yVAf(x),g(x,y)VB ,

  2. f(x),zVBx,h(x,z)VA

Czy te redukcje są równoważne?


Myślę, że dwie definicje są równoważne. Dla dwóch językówNPA iB , jeżelijest Karp zredukować do B , a następniejest Levin zredukować do B .ABAB

Oto mój dowód:

Niech i ¯ x być dowolne instancje A gdy x ' być, że z B . Załóżmy V i V B są weryfikatorzy z A i B . Niech Y i Ż Y być dowolne certyfikaty x i Ż x w zależności od V A . Niech z będzie, że od X " zgodnie z V B .xx¯AxBVAVBAByy¯xx¯VAzxVB

Skonstruować nowe weryfikatorów and V " B o nowe certyfikaty, Y ' i Z ' :VAVByz

VA(x,y):

  1. : jeśli f ( x ) f ( Ż x ) , odrzucenia. W przeciwnym razie wyprowadzić V A ( ¯ x , ¯ y ) .y=0,x¯,y¯f(x)f(x¯)VA(x¯,y¯)
  2. : Wyjście V B ( F ( x ) , z ) .y=1,zVB(f(x),z)

VB(x,z):

  1. : Wyjście V B ( x ' , oo ) .z=0,zVB(x,z)

  2. : jeśli x 'f ( x ) , odrzucenia. W przeciwnym razie wyprowadzić V A ( x , y ) .z=1,x,yxf(x)VA(x,y)

Funkcje obliczane w czasie wielomianowym i h są zdefiniowane jak poniżej:gh

g(x,y)

  1. : Wyjście1 , Ż x , Ż Y .y=0,x¯,y¯1,x¯,y¯

  2. : Wyjście0 , oo .y=1,z0,z

h(x,z)

  1. : Wyjście1 , z .z=0,z1,z

  2. : Wyjście0 , x , y .z=1,x,y0,x,y

Niech oznacza zbiór wszystkich certyfikatów X według V A , a Z x " oznacza zbiór wszystkich certyfikatów X ' zgodnie V B . Zatem zestaw wszystkich certyfikatów x według V A wynosi 0 ¯ x Y ¯ x + 1 Z f ( x ) tak, że f ( x ) = f ( ¯ x )YxxVAZxxVBxVA0x¯Yx¯+1Zf(x)f(x)=f(x¯), a zestaw wszystkich certyfikatów zgodnie z V B wynosi 0 Z x + 1 ¯ x Y ¯ x, tak że x = f ( ¯ x ) .xVB0Zx+1x¯Yx¯x=f(x¯)

(Pochodzi z języka akceptującego i V B. )VAVB

Teraz niech , reszta jest łatwa do sprawdzenia.x=f(x)

cc
źródło
Przed udowodnieniem roszczenia powinieneś zdefiniować, co to znaczy, że język jest Levinem redukowalnym do innego.
Tsuyoshi Ito

Odpowiedzi:

14

Nie. Pierwsza uwaga, że ​​redukcja Levina ma sens tylko w odniesieniu do klas, które certyfikat ma znaczenie, np. podczas gdy redukcja Karp jest ogólna. Słowo „certyfikat” dla problemu ma sens tylko wtedy, gdy weryfikator jest naprawiony. Redukcja Levina zakłada, że ​​weryfikatory są naprawione. Nie możesz zmienić weryfikatorów. (Poniżej zakładam, że weryfikatory certyfikatów są ustalone zgodnie z definicją redukcji Levina).NP

Po drugie, redukcja Levina oznacza, że ​​można znaleźć certyfikat dla jednego z certyfikatu dla drugiego. Prawdą jest, że dobrze znanymi redukcjami karpów między problemami naturalnymi okazują się redukcje Levina, ale nie musi to być prawda w ogóle.

Jeśli możemy zredukować przypadki problemu do problemu B , nie oznacza to, że mamy sposób na obliczenie certyfikatu dla jednego z certyfikatu dla drugiego.AB

Aby było to prawdą, potrzebujemy faktu, że problem wyszukiwania certyfikatu odpowiadający problemowi decyzyjnemu jest czasem wielomianowym redukującym się do problemu decyzyjnego. Jest to prawdziwe w odniesieniu do problemów, ale nie wiadomo, że ogólnie prawdą nawet N P problemów.NP-completeNP

Kaveh
źródło
Zgadzam się z twoim pierwszym punktem, że redukcja Karp jest bardziej ogólna niż redukcja Karp. Zgodnie z nim myślę, że mój problem powinien zostać zmodyfikowany jako „Niech i L 2 będą dwoma językami w N P. Jeśli L 1 oznacza Karp redukowalny do L 2 , to L 1 jest redukowalny do L2 do L 2 ”. Nie zgadzam się jednak z pozostałymi komentarzami. L1L2NPL1L2L1L2
cc
W moim udowodnieniu, najpierw i L 2 będą dowolnymi takimi dwoma językami. Ponieważ są w N P , istnieją P TM M 1 i M 2 . Dla każdego wystąpienia x L 1 zestaw wszystkich certyfikatów to Y x dla T M 1 . Podobnie definiujemy Z x dla x L 2 . Ponieważ L 1 jest Karpem redukowalnym do L 2 , istnieje takie fL1L2NPM1M2xL1YxTM1ZxxL2L1L2fjak zdefiniowano.
cc
Teraz skonstruowaliśmy nowe i M 2 . Dla każdej instancji x L 1 nowy zestaw wszystkich certyfikatów to 0 Y x + 1 Z f ( x ) , podczas gdy dla każdej instancji f ( x ) L 2 nowy zestaw wszystkich certyfikatów to 0 Z f ( x ) + 1 x Y x . (Tutaj używamy wyrażeń regularnych) Są to legalne i wszystkie certyfikatyM1M2xL10Yx+1Zf(x)f(x)L20Zf(x)+1xYx i M 2 . Nawiasem mówiąc, to funkcji P g i h , jak zdefiniowano przekształcić wszystkie możliwe certyfikatu z jednym problemem do drugiej. M1M2gh
cc
ps: Nie musimy podawać transformacji z gdzie nie ma x L 1, tak że x = f ( x ) , ponieważ redukcje Karp i Levin są zarówno mapowaniami wiele do jednego. Myślę, że to może odpowiedzieć na ostatni akapit. xL2xL1x=f(x)
cc
@cc wydaje się, że nadal myślisz, że możesz zmienić weryfikatory, nie możesz, definicja redukcji Levina dotyczy problemów z wyszukiwaniem, tj. weryfikatory są naprawione.
Kaveh
5

Szybkie kontrprzykład dla dowodu: załóżmy, że , f ( x 1 ) = f ( x 2 ) L 2 , oraz w to ważny certyfikat dla x 1 , ale nie dla x 2x1,x2L1f(x1)=f(x2)L2wx1x2

M1(x1,0,w)=M1(x1,w)=1

M1(x2,0,w)=M1(x2,w)=0

Z definicji g(x1,0,w)=1,x1,w

tak, M ' 2 ( f ( x 2 ) , 1 , x 1 , w ) ) = K 1 ( x 1 , w ) = 1 to1 , x 1 , w jest ważny certyfikat f ( x 2 )f(x1)=f(x2)M2(f(x2),1,x1,w))=M1(x1,w)=11,x1,wf(x2) ale

która nie jest ważny certyfikat x 2h(f(x2),1,x1,w)=0,wx2

Vor
źródło
Bardzo dziękuję za wskazanie kontrprzykładu. Zmodyfikowałem konstrukcję i myślę, że teraz działa. Czy mógłbyś na to rzucić okiem?
cc