Rodzaje redukcji i powiązane definicje twardości

15

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 BZAbZAbZAM.ZAbOb

  • Redukcja Turinga: może wykonać wiele zapytań do . O BM.ZAOb

  • 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 BObObP.ZA=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 BmM.ZAOBOBm

    AmB jeśli sposób obliczeniowy funkcji tak, że .f : Σ Σ f ( x ) Bf:ΣΣf(x)BxA

  • 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 mOBmp

    AmpB jeśli w poli czasie funkcji obliczeniowy tak, że .f:ΣΣf(x)BxA

  • 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ę)AB1p

    A1pB jeśli w poli czasie obliczalną bijection tak, że .f:ΣΣf(x)BxA

    Te redukcje pozwalają zachować liczbę rozwiązań. Stąd .#MA=#OB

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.

Pavithran Iyer
źródło

Odpowiedzi:

7

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

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

Zauważ, że #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.

Kaveh
źródło
Niestety, wydaje mi się, że wymieniłem terminologię „Karp redukcja” i „Redukcja gotowanie”. Jeśli go wymienię, pasuje do twoich odpowiedzi. Dzięki. Jeśli chodzi o oszczędne redukcje, czy mówisz, że nie zachowują one liczby „rozwiązań”? Jeśli tak, to widzę w Twierdzeniu 17.10 Arory i Baraka (Strona 299), że skąpe redukcje rzeczywiście zachowują liczbę rozwiązań. Kolejne odniesienie: ( cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L10.pdf )
Pavithran Iyer
Tutaj mówi o oszczędnym zmniejszeniu z L do SAT, odwzorowuje każdą instancję x L na unikalną instancję SAT (to znaczy, mapa redukcyjna to jeden-jeden): [ cse.cuhk.edu.hk/~andrejb/csc5170/notes /10L10.pdf] . Czy nie należy zakładać, że jeśli liczba rozwiązań zostanie zachowana przez redukcję, to mapa jest jedna?
Pavithran Iyer
@Pavithran, to, co napisałeś w swoim pytaniu, nie było definicją skąpych redukcji. Aby uzyskać odpowiedź, zobacz ćwiczenie 2.13 w ich książce.
Kaveh
0

Ob

Björn Lindqvist
źródło
W szczególności zmieniono definicje redukcji Cooka i Karp.
David Richerby