Problemy poza P, które nie są P-trudne

Czytając odpowiedź Petera Shora i wcześniejsze pytanie Adama Crume'a, zdałem sobie sprawę, że mam pewne nieporozumienia na temat tego, co to znaczy być $\mathsf{P}$ twardym.

Problemem jest $\mathsf{P}$ -hard jeśli jakiś problem w $\mathsf{P}$ sprowadza się do niego z $\mathsf{L}$ (lub jeśli wolisz $\mathsf{NC}$ ) obniżek. Problem występuje poza $\mathsf{P}$ jeśli nie istnieje algorytm wielomianowy do jego rozwiązania. Oznacza to, że powinien występować problem, który znajduje się poza $\mathsf{P}$ ale nie jest $\mathsf{P}$ twardy. Jeśli założymy, że FACTORING jest poza $\mathsf{P}$ , to odpowiedź Petera Shora sugeruje, że FACTORING może być takim problemem.

Czy są jakieś znane problemy (naturalne lub sztuczne), o których wiadomo, że leżą poza $\mathsf{P}$ ale nie są $\mathsf{P}$ twarde? A co z założeniami słabszymi niż założenie faktoringowe? Czy istnieje nazwa tej klasy złożoności?

cc.complexity-theory complexity-classes Artem Kaznatcheev
źródło

Odpowiedzi:

Jeśli $\mathsf{P} \neq \mathsf{L}$ to żaden zestaw rzadki (nawet nieprzenikalny) nie może być $\mathsf{P\text{-}hard}$ .

Błędne przekonanie pochodzi z myślenia o klasach złożoności (i problemach obliczeniowych) jako tworzeniu porządku liniowego, co nie jest prawdą. Użycie słowa „twardość” dla problemu może być użyte do rozwiązania innych problemów w klasie, co również przyczynia się do błędnego przekonania. Dolna granica dla problemu (tj. Nie znajdowanie się w klasie złożoności) nie oznacza, że problem jest trudny dla klasy (tzn. Może być wykorzystany do rozwiązania innych problemów w klasie). Nie wiem, czy istnieje obecnie lepsza alternatywna terminologia dotycząca „twardości”, która była używana w poprzednich dziesięcioleciach to „uniwersalność” (która, IMHO, wyraziła tę koncepcję bardziej wiernie, a wtedy moglibyśmy zastosować „twardość” za brak bycia w klasie, ale zmiana ustalonej terminologii jest bardzo trudna).

Kaveh
źródło

niektóre diagramy Eulera dotyczące klas złożoności podsunęły mi także drugie nieporozumienie, co, jak sądzę, spowodowało moje zamieszanie dotyczące twardości X.

Artem Kaznatcheev

@Artem, tak, to także czynnik. Oto, co robię na zajęciach: Wspominam o nieporównywalności redukcji i pod , mając nadzieję, że pomoże to uczniom uniknąć myślenia, że wszystko jest uporządkowane liniowo.

\mod p

$\mod p$

\mod q

$\mod q$

A C^{0}

$\mathsf{AC^0}$

Kaveh

część zamówienia, z którą mam znacznie mniej problemów. W szczególności uważam, że NP i coNP są wystarczająco dobre, aby pokazać, że nie powinniśmy myśleć o klasach złożoności mających całkowity porządek.

Artem Kaznatcheev

@Artem, dobra uwaga (choć nie możemy udowodnić, że się różnią). Myślę, że jedną z przyczyn tej terminologii jest brak rozsądnych dolnych granic, nie mamy dobrego ograniczenia dla SAT, ale uważamy, że trudno jest go rozwiązać, ponieważ jest uniwersalny, ale słowo „uniwersalny” nie stwarzać takie same trudności, jak „trudne”, zwłaszcza osobom niebędącym ekspertami. Ale to stwarza problem, ponieważ chociaż można argumentować, że uniwersalność problemu oznacza, że problem jest trudny do rozwiązania, trudność jego rozwiązania nie oznacza, że problem jest uniwersalny.

Kaveh

tzn. uniwersalne problemy są trudne (przynajmniej tak trudne jak każdy problem w klasie), ale trudne problemy nie muszą być uniwersalne.

Kaveh

Myślę, że można zbudować zestaw nie w który nie jest twardy za pomocą argumentu w stylu Ladnera. Oto konkretny przykład. $P$ $P$

W swojej pracy „Jednolite podejście do uzyskania zestawów diagonalnych w klasach złożoności” (Theor. Comp. Sci. 18, 1982) Schöning udowadnia, co następuje:

Twierdzenie Załóżmy, że , , i są klasami złożoności prezentowanymi rekurencyjnie i są zamknięte w wariacjach skończonych. Następnie jest zestaw taki, że , , a jeśli i nie jest trywialny (pusty zbiór lub wszystkie ciągi), wówczas jest polimeime wiele razy jeden redukowany do . $A_1 \notin C_1$ $A_2 \notin C_2$ $C_1$ $C_2$ $A$ $A \notin C_1$ $A \notin C_2$ $A_1 \in P$ $A_2$ $A$ $A_2$

W tym celu stosuje się, zestaw być zbiór pusty, a być -Complete pod redukcji polytime ustaw będzie zbiorem zestawów -hard które są w , określonych . Pustym zestawem nie może być twardość (definicja twardości dla języka wymaga, aby istniała co najmniej jedna instancja w tym języku i jedna instancja nie w). zdecydowanie nie znajduje się w . i można zweryfikować spełniają powyższe warunki (podobny do tego, jak Schoening robi dla $A_1$ $A_2$ $EXP$ $C_1$ $P$ $EXP$ $C_2 = P$ $P$ $P$ $A_2$ $C_2$ $C_1$ $C_2$ $NP$ -kompletne zestawy; patrz także powiązane pytanie ). Tak więc otrzymujemy że nie jest -hard problem , a nie jest w . Ponieważ jednak a jest , jest wielokrotnością redukowalną do zestawu pełnego , więc jest w . Dlatego w szczególności nie może być również twardy. $A$ $P$ $EXP$ $A$ $P$ $A_1 \in P$ $A_2$ $A$ $EXP$ $EXP$ $A$ $P$

W powyższej argumentacji, ograniczenie do problemów -hard w jest niezbędne do zapewnienia rekurencyjną presentability, ponieważ problemy P-hard jako całość nie rekurencyjnie reprezentacyjny i nawet nie przeliczalny . „Naturalne” przykłady tego to inna historia ... $P$ $EXP$

Ryan Williams
źródło

Lubię, jak to przechodzi nawet jeśli . Chyba że coś źle zrozumiałem.

L = P

$L = P$

Artem Kaznatcheev

@Artem: Jeśli weźmiesz pod uwagę twardość przy ograniczaniu przestrzeni logów, to każdy nietrywialny język jest L-trudny. Dlatego, jeśli L = P, nie ma języków poza P, które są P-twarde przy redukcji przestrzeni logarytmicznej.

Tsuyoshi Ito

Innym sposobem generowania problemów, które są poza P, ale nie P-trudnych, jest wzięcie kompletnych problemów dla klas nieporównywalnych z P. Powiedzmy, że klasa X jest nieporównywalna z P, w tym sensie, że żaden z nich nie jest podzbiorem. Wtedy problem z kompletnym X jest koniecznie poza P (inaczej P zawiera X) i nie jest P-twardy (w przeciwnym razie X obejmuje P).

Próbowałem myśleć o niektórych klasach nieporównywalnych z P, ale P jest dość solidną klasą, więc nie ma zbyt wielu takich klas. Na przykład RNC i QNC mogą być nieporównywalne z P. DSPACE ( ) mogą być również nieporównywalne z P. PolyL jest nieporównywalne z P, ale nie ma pełnych problemów w przypadku zmniejszenia przestrzeni logów. $\log^2$

Robin Kothari
źródło

Moim zdaniem jest to prawie to samo pytanie sformułowane inaczej i niekoniecznie jest to sposób na udzielenie odpowiedzi na to pytanie. W rzeczywistości język A nie jest ani w P, ani w P-trudny tylko wtedy, gdy klasa języków redukowalnych do A jest nieporównywalna z P (weź swoje ulubione pojęcie redukowalności). Jeśli chodzi o obecne pytanie, myślę, że bardziej prawdopodobne jest, że będzie ono przydatne w przeciwnym kierunku; to jest inny sposób interpretacji odpowiedzi na bieżące pytanie.

Tsuyoshi Ito