Dlaczego problemy związane z NPI nie są jednakowo skomplikowane?

Jak spojrzeć na problem i powód, dla którego jest to NP-średniozaawansowany, a nie NP-pełny? Często dość łatwo jest spojrzeć na problem i stwierdzić, czy jest to prawdopodobnie NP-Complete, czy nie, ale wydaje mi się, że znacznie trudniej jest stwierdzić, czy problem dotyczy NP-Intermediate, ponieważ linia wydaje się dość cienka między tymi dwoma zajęcia Zasadniczo pytam, dlaczego problem, który można zweryfikować w czasie wielomianowym (jeśli w ogóle), ale nie zostanie rozwiązany w czasie wielomianowym (o ile P nie jest równe NP), nie byłby czasem wielomianowym redukowalnym względem siebie. Ponadto, czy jest jakiś sposób na wykazanie, że problem jest średniozaawansowany NP podobny do tego, jak problem wykazuje trudność NP, taki jak redukcja lub inna technika? Doceniamy również wszelkie linki lub podręczniki, które pomogłyby mi zrozumieć klasę NP-Intermediate.

cc.complexity-theory complexity-classes np-intermediate Jesse Stern
źródło

„problem, który można rozwiązać w czasie wielomianowym”, myślę, że masz na myśli „problem, który można zweryfikować w czasie wielomianowym”.

Kaveh

Istnieje klasa problemów z GI, które są wielomianowo równoważne z Graph Isomorphism. Zakłada się, że GI jest poważnym problemem będącym pośrednim NP

Mohammad Al-Turkistany,

Przy okazji, tytuł wprowadza w błąd, równość dwóch problemów złożoności w odniesieniu do redukcji (np. Redukcji Karp) jest już zdefiniowana, sugerowałbym, aby zmienić ją na coś w rodzaju „Dlaczego problemy NPI nie są tej samej złożoności?”.

Kaveh

@kaveh Dokonano wszystkich zmian. Dzięki za kolejną świetną odpowiedź!

Jesse Stern

„Często dość łatwo jest spojrzeć na problem i stwierdzić, czy jest to NP-Complete, czy nie”. IMHO, to nie może być dalsze od prawdy!

Mahdi Cheraghchi,

Odpowiedzi:

Nie można pokazać, że problemem jest bez oddzielenia od . $\mathsf{NPI}$ $\mathsf{P}$ $\mathsf{NP}$

Istnieją sztuczne problemy, które można udowodnić w przy użyciu uogólnień twierdzenia Landera (patrz także to ), zakładając, że . $\mathsf{NPI}$ $\mathsf{NP}\neq\mathsf{P}$

Również wersją problemów z są $\mathsf{NEXP\text{-}complete}$ $\mathsf{NPI}$ przy założeniu, że (zobacz także to i to ). $\mathsf{NEXP} \neq \mathsf{EXP}$

Problem w jest często przypuszczany, że to gdy: $\mathsf{NP}$ $\mathsf{NPI}$

możemy wykazać przy rozsądnych założeniach, że nie jest to ale nie wiadomo, że jest w , $\mathsf{NPC}$ $\mathsf{P}$
możemy wykazać przy rozsądnych założeniach, że nie ma go w ale nie jest znany w , $\mathsf{P}$ $\mathsf{NPC}$

a czasami właśnie wtedy, gdy nie możemy pokazać, że jest w lub . $\mathsf{NPC}$ $\mathsf{P}$

Przykładem rozsądnego założenia jest wykładnicza hipoteza czasowa (lub niektóre inne założenia twardości obliczeniowej ).

Zasadniczo pytam, dlaczego problem, który może zostać rozwiązany w czasie wielomianowym (jeśli w ogóle), ale nie rozwiązany w czasie wielomianowym (o ile P nie jest równe NP), nie byłby czasem wielomianowym redukowalnym względem siebie.

Nie rozumiem, dlaczego można by oczekiwać, że to prawda. W każdym razie, zakładając, że wynika z twierdzenia Landera, że istnieje nieskończenie wiele poziomów stopni między i . $\mathsf{NPC}\not \subseteq \mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{NP}$

Kaveh
źródło

„2. możemy wykazać przy rozsądnych założeniach, że nie ma go w P, ale nie wiadomo, że jest w NP„ Nie masz na myśli „… w NPC”?

Tyson Williams,

@Victor, nie, nie wiadomo, że nie jest równy , a są różne iff i są różne. Cofam zmianę.

P

$\mathsf{P}$

N P C

$\mathsf{NPC}$

P

$\mathsf{P}$

N P

$\mathsf{NP}$

Kaveh

@Kaveh, myślę, że myślał o trywialnych językach ( i ), ale wykluczasz je z P.

\emptyset

$\emptyset$

{0, 1}^{*}

$\{0,1\}^*$

didest

@Diego, cóż, nic nie jest dla nich redukowalne, ale masz rację. Naprawię to.

Kaveh

@Kaveh and Diego: Tak, myślałem o tych trywialnych językach.

Victor Stafusa,

Typowy przypadek występuje wtedy, gdy problem z leży również w lub . Zakładając, że hierarchia wielomianowa się nie zwija, takim problemem nie może być -complete. Przykłady obejmują rozkład na czynniki całkowite, logarytm dyskretny, izomorfizm wykresów, niektóre problemy z siecią itp. $\mathsf{NP}$ $\mathsf{coNP}$ $\mathsf{coAM}$ $\mathsf{NP}$

Mahdi Cheraghchi
źródło

Innym typowym przypadkiem problemu jest występowanie świadka o długości ale mniejszej niż . Problem istnienia kliki o rozmiarze na wykresie jest typowym przykładem - w tym przypadku świadek (konkretna klika) wymaga bitów . $NPI$ $\omega(\log n)$ $n^{O(1)}$ $\log n$ $O(\log^2 n)$

Zakładając hipotezę o wykładniczym czasie, taki problem jest łatwiejszy niż problem - (który wymaga czasu ), ale trudniejszy niż problem czasu wielomianowego. $NP$ $\exp(n^{O(1)})$

David Harris
źródło