Mam tylko szybkie pytanie. Jeśli mamy dwie problemy z decyzjami, powiedzmy L1 i L2. Jeśli L1 i może być zredukowany do L2 w czasie wielomianu, czy to prawda, że L2 NIE MOŻE zostać zredukowane do L1 w czasie wielomianowym?
Rozumiem, że oznaczałoby to:
L1 can be reduced to L2 in polynomial time => NOT (L2 can be reduced to L1 in polynomial time)
=(L1 not in P) & (L2 in P) => (L1 in P) & (L2 not in P)
=[(L1 in P) OR (L2 not in P)] OR [(L1 in P) & L2 in P)]
=(L1 in P) OR (L2 not in P)
Tak więc stwierdzenie, że L1 można zredukować do L2 wCzas polityczny oznacza, że L2 nie może zostać zredukowane do L1 w czasie działania w czasie, jest prawdziwe tylko wtedy, gdy L1 jest w P lub jeśli L2 nie jest w P. Tak jak tam, jeśli tak nie jest, wtedy instrukcja jest fałszywa.
Czy moja logika ma sens, czy jestem daleko? Każda rada lub pomoc będą mile widziane. Dziękuję Ci!
Odpowiedzi:
1 dla odpowiedzi № 1Ogólne stwierdzenie "jeśli L1 czas wieloczynnościowy zmniejsza się do L2, a następnie L2 nie zmniejsza się do L1"jest generalnie nieprawidłowa, jakiekolwiek dwa problemy w P (z wyjątkiem ∅ i Σ *) są sprowadzane wielokrotnie do siebie: wystarczy rozwiązać problem w czasie wielomianowym i wypisać odpowiedź tak lub nie w zależności od potrzeb.
Twoja szczególna logika jest niepoprawna, ponieważ redukuje się czas wielomianu między dwoma problemami nie zagwarantować cokolwiek na temat tego, czy językisą w P lub nie. Na przykład, problem zatrzymania jest sprowadzany wielomianowo do problemu, czy TM akceptuje dany ciąg, ale żaden problem nie występuje w P, ponieważ żaden problem nie jest rozstrzygalny.
Mam nadzieję że to pomoże!