Rodzaje redukcji i powiązane definicje twardości

Niech A będzie sprowadzić do punktu B, czyli . Stąd, maszyna Turinga akceptując ma dostęp do Oracle dla . Niech maszyna Turinga akceptująca będzie a wyrocznia dla będzie . Rodzaje obniżek:A B A M A B O $A \leq B$$A$$B$$A$$M_{A}$$B$$O_{B}$

• Redukcja Turinga: może wykonać wiele zapytań do . O $M_{A}$$O_{B}$

• Redukcja karpia: zwana również „redukcją Turinga w czasie wielomianowym”: Dane wejściowe do muszą być konstruowane w czasie polytime. Ponadto liczba zapytań do musi być ograniczona wielomianem. W takim przypadku: . O B P A = P $O_{B}$$O_{B}$$P^{A} = P^{B}$

• Wielokrotna redukcja Turinga: może wykonać tylko jedno zapytanie do , podczas ostatniego kroku. Dlatego odpowiedzi wyroczni nie można modyfikować. Jednak czas potrzebny na skonstruowanie danych wejściowych do nie musi być ograniczony przez wielomian. Równoważnie: ( oznaczający redukcję wielokrotności) O B O B ≤ $M_{A}$$O_{B}$$O_{B}$$\leq_{m}$

  $A \leq_{m} B$ jeśli sposób obliczeniowy funkcji tak, że .f : Σ ∗ → Σ ∗ f ( x ) ∈ $\exists$$f: \Sigma^{\ast} \to \Sigma^{\ast}$$f(x) \in B \iff x\in A$

• Redukcja Cooka: Zwana także „redukcją czasu wielomianowego jeden-jeden”: Redukcja wielokrotna jeden, w której czas potrzebny do skonstruowania danych wejściowych do musi być ograniczony przez wielomian. Równoważnie: ( oznaczający redukcję wielokrotności) ≤ p $O_{B}$$\leq^{p}_{m}$

  $A \leq^p_{m} B$ jeśli w poli czasie funkcji obliczeniowy tak, że .$\exists$$f: \Sigma^{\ast} \to \Sigma^{\ast}$$f(x) \in B \iff x\in A$

• Redukcja parsimonious: Nazywany również „wielomian razem jeden jeden redukcja”: zmniejszenie kucharz gdzie każdy przypadek odwzorowany unikalnej instancji . Równoważnie: ( oznaczający oszczędną redukcję)$A$$B$$\leq^{p}_{1}$

  $A \leq^p_{1} B$ jeśli w poli czasie obliczalną bijection tak, że .$\exists$$f: \Sigma^{\ast} \to \Sigma^{\ast}$$f(x) \in B \iff x\in A$

  Te redukcje pozwalają zachować liczbę rozwiązań. Stąd .$\#M_{A} = \#O_{B}$

Możemy zdefiniować więcej rodzajów redukcji, ograniczając liczbę zapytań o wyrocznię, ale pomijając je, czy ktoś mógłby mi uprzejmie powiedzieć, czy poprawnie otrzymałem nomenklaturę różnych rodzajów redukcji. Czy zdefiniowano problemy NP-zupełne w odniesieniu do redukcji Cooka lub redukcji oszczędnej? Czy ktoś może uprzejmie podać przykład problemu, który jest kompletny NP w ramach Cooka, a nie w przypadku zbytniej redukcji.

Jeśli się nie mylę, klasa # P-Complete jest zdefiniowana w odniesieniu do redukcji Karp.

Twoja definicja oszczędnych redukcji jest nieprawidłowa. Mylisz to z jednorazowymi wielomianowymi redukcjami, co jest szczególnym przypadkiem redukcji Karp. Nie zachowują liczby „rozwiązań”. Proszę zobaczyć tę odpowiedź, aby uzyskać więcej informacji na temat redukcji uwzględniających liczbę certyfikatów.

Reszta wydaje się w porządku, chociaż zwykle lepiej jest oglądać je na dwuwymiarowej mapie:

• złożoność redukcji: obliczalna, czas wielomianowy, przestrzeń logarytmiczna itp.
• rodzaj dostępu: Turing, wiele-jeden, jeden-jeden itp.

Czy zdefiniowano problemy NP-zupełne w odniesieniu do redukcji Cooka lub redukcji oszczędnej?

Twardość i kompletność P są zdefiniowane przeciwko redukcjom Karp (polytime-one-one), a nie Cookowi ani redukcjom oszczędnym.$\mathsf{NP}$

Czy ktoś może uprzejmie podać przykład problemu, który jest kompletny NP w ramach Cooka, a nie w przypadku zbytniej redukcji.

Weź dopełnienie SAT, czy jest ono kompletne dla ramach redukcji Cooka, nie uważa się za zakończoną na N P ramach redukcji Karp. Redukcje karp obejmują redukcje czasu polytime one-one.$\mathsf{NP}$$\mathsf{NP}$

klasa # P-Complete jest zdefiniowana w odniesieniu do redukcji Karp

Zauważ, że $\mathsf{\#P}$ nie jest klasą problemów decyzyjnych, jest klasą problemów obliczeniowych funkcji. Jego twardość i kompletność są zwykle definiowane wrt Ograniczenia gotowania (polime Turing). Patrz np. Arora i Barak, strona 346.

$O_B$