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, .
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, że
,
Czy te redukcje są równoważne?
Myślę, że dwie definicje są równoważne. Dla dwóch języków i , jeżelijest Karp zredukować do B , a następniejest Levin zredukować do B .
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 .
Skonstruować nowe weryfikatorów and V " B o nowe certyfikaty, Y ' i Z ' :
- : jeśli f ( x ) ≠ f ( Ż x ) , odrzucenia. W przeciwnym razie wyprowadzić V A ( ¯ x , ¯ y ) .
- : Wyjście V B ( F ( x ) , z ) .
: Wyjście V B ( x ' , oo ) .
: jeśli x ' ≠ f ( x ) , odrzucenia. W przeciwnym razie wyprowadzić V A ( x , y ) .
Funkcje obliczane w czasie wielomianowym i h są zdefiniowane jak poniżej:
: Wyjście ⟨ 1 , Ż x , Ż Y ⟩ .
: Wyjście ⟨ 0 , oo ⟩ .
: Wyjście ⟨ 1 , z ⟩ .
: Wyjście ⟨ 0 , 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 ), a zestaw wszystkich certyfikatów zgodnie z V ′ B wynosi 0 Z x ′ + 1 ¯ x Y ¯ x, tak że x ′ = f ( ¯ x ) .
(Pochodzi z języka akceptującego i V ′ B. )
Teraz niech , reszta jest łatwa do sprawdzenia.
Odpowiedzi:
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.A B
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-complete NP
źródło
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,x2∈L1 f(x1)=f(x2)∈L2 w x1 x2
Z definicjig(x1,⟨0,w⟩)=⟨1,x1,w⟩
tak, M ' 2 ( f ( x 2 ) , ⟨ 1 , x 1 , w ⟩ ) ) = K 1 ( x 1 , w ) = 1 to ⟨ 1 , x 1 , w ⟩ jest ważny certyfikat f ( x 2 )f(x1)=f(x2) M′2(f(x2),⟨1,x1,w⟩))=M1(x1,w)=1 ⟨1,x1,w⟩ f(x2) ale
która nie jest ważny certyfikat x 2h(f(x2),⟨1,x1,w⟩)=⟨0,w⟩ x2
źródło