Intuicja dla klasy UP

Klasa UP jest zdefiniowana jako taka:

Klasa problemów decyzyjnych rozwiązanych przez maszynę NP, taką jak

Jeśli odpowiedź brzmi „tak”, akceptuje dokładnie jedną ścieżkę obliczeniową.

Jeśli odpowiedź brzmi „nie”, wszystkie ścieżki obliczeniowe odrzucają.

Próbuję rozwinąć intuicję dla tej definicji.

Czy można powiedzieć, że problemy UP są problemami z unikalnymi rozwiązaniami (np. Rozkład na czynniki pierwsze)?

Wydaje mi się to bliskie prawdy; ale nie mogę oprzeć się wrażeniu, że to oznaczałoby, gdyż UP zawiera P i jest zawarta w NP, że w przypadku P = NPchcielibyśmy dostać, że P = UP = NP, więc wszystkie problemy NPmają unikalne rozwiązania, a także, co wydaje się czymś provably nie prawda: P != NPprzez reductio ad absurdum. Mam nadzieję, że w tym akapicie nie ma zbyt wiele domysłów i machania ręką dla twojego gustu.

Twój zamieszanie wydaje się być faktem, że problemy mają więcej niż jeden sposób, aby zdefiniować „rozwiązanie” (lub świadków). Rodzaj rozwiązania nie jest częścią definicji problemu. Na przykład w przypadku kolorowania graficznego oczywistym rodzajem rozwiązania jest przypisanie jednego koloru do każdego wierzchołka (przy użyciu co najwyżej wymaganej liczby kolorów); jednak według twierdzenia Gallai – Hasse – Roy – Vitaver$\mathsf{NP}$innym rodzajem rozwiązania, które działa równie dobrze, jest przypisanie orientacji do każdej krawędzi (tworzenie ukierunkowanych ścieżek co najwyżej wymaganej liczby wierzchołków). Te dwa typy rozwiązań można sprawdzić w czasie wielomianowym, ale za pomocą różnych algorytmów, a także mają różne właściwości kombinatoryczne. Na przykład w typowym przypadku problemowym liczba przypisań kolorów wierzchołków będzie inna niż liczba orientacji krawędzi. Wiele badań dotyczących przyspieszenia algorytmów wykładniczych dla problemów typu NP można interpretować jako znalezienie nowej rodziny rozwiązań tego samego problemu, który ma mniej możliwości sprawdzenia.

Każdy problem w ma „rozwiązanie” N P składające się tylko z pustego ciągu. Aby sprawdzić, czy jest to rozwiązanie, po prostu sprawdź, czy ciąg rozwiązania jest pusty, a następnie uruchom algorytm czasu wielomianowego dla wystąpienia problemu. Z tego typu rozwiązania, każdy przypadek tak ma dokładnie jedno rozwiązanie ważny i każdy przypadek nie ma zera, spełniające definicję U P i pokazując, że P ⊂ U P . Jeśli P = N P, to samo rozwiązanie pustych ciągów będzie również działać dla każdego problemu w N P , pokazując, że N P = U $\mathsf{P}$$\mathsf{NP}$$\mathsf{UP}$$\mathsf{P}\subset\mathsf{UP}$$\mathsf{P}=\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}=\mathsf{UP}$. Nie ma zatem sprzeczności między faktem, że rozwiązanie z ciągiem pustym jest unikalne, a faktem, że jakiś inny rodzaj rozwiązania tego samego problemu nie jest unikalny.

$\mathsf{UP}$$\mathsf{NP}$$\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

$\mathsf{NPMV}$$\mathsf{NP}$

$\mathsf{NPSV}$$\mathsf{NPMV}$

$\mathsf{NP}$$\mathsf{NPMV}$$\mathsf{NPSV}$$\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

$\mathsf{UP}$$\mathsf{NP} = \mathsf{UP}$$L \in \mathsf{NP}$$\mathsf{UP}$$L$$\mathsf{NP}$$L$