W artykule Złożoność problemu Frobeniusa autorstwa Ramíreza-Alfonsína okazało się, że problemem jest NP-zupełność za pomocą redukcji Turinga. Czy to jest możliwe? Jak dokładnie? Myślałem, że było to możliwe tylko w przypadku wielomianowego wielokrotnego zmniejszenia. Czy są jakieś odniesienia na ten temat?
Czy istnieją dwa różne pojęcia twardości NP, a nawet kompletności NP? Ale wtedy jestem zdezorientowany, ponieważ z praktycznego punktu widzenia, jeśli chcę wykazać, że mój problem jest trudny do przeprowadzenia w NP, którego używam?
Rozpoczęli opis w następujący sposób:
Wielomianowa redukcja Turinga z czasu do innego problemu P 2 jest algorytmem A, który rozwiązuje P 1 za pomocą hipotetycznego podprogramu A 'do rozwiązania P 2, tak że jeśli A' byłby algorytmem wielomianowym dla P 2, to A byłby algorytmem wielomianowym dla P 1 . Mówimy, że P 1 można zredukować Turinga do P 2 .
Problem nazywa się (Turing) NP-trudny, jeśli występuje problem decyzji P 2 dla NP kompletny, taki jak może być zredukowana do Turinga P 1 .
Następnie używają takiej redukcji Turinga od problemu NP-zupełności, aby pokazać NP NP jakiegoś innego problemu.
źródło
W porządku. Wielomianowa redukcja Turinga jest redukcją Cooka (jak w twierdzeniu Cooka-Levina), a redukcja problemu NP-zupełnego do nowego problemu daje twardość NP (podobnie jak redukcja wielomianowa Tiema, redukcja AKA Karp). Rzeczywiście, redukcje Karp są po prostu ograniczone Redukcje Turinga.
Różnią się (w odniesieniu do tego pytania) w wykazaniu członkostwa. Zmniejszenie Karp od problemu do problemu w NP pokazuje, że pierwszy jest w NP. Zmniejszenie gotowania w tym samym kierunku nie.
źródło