Naturalni kandydaci do hierarchii wewnątrz NPI

Załóżmy, że . to klasa problemów w które nie są ani w ani w -hard. Listę problemów, które mogą być tutaj . $\mathsf{P} \neq \mathsf{NP}$ $\mathsf{NPI}$ $\mathsf{NP}$ $\mathsf{P}$ $\mathsf{NP}$ $\mathsf{NPI}$

Twierdzenie Ladnera mówi nam, że jeśli wówczas istnieje nieskończona hierarchia problemów , tzn. Istnieją problemy , które są trudniejsze niż inne problemy. $\mathsf{NP}\neq\mathsf{P}$ $\mathsf{NPI}$ $\mathsf{NPI}$ $\mathsf{NPI}$

Szukam kandydatów na takie problemy, tzn. Interesują mnie pary problemów
- , - i są przypuszczalne, że są , - jest znane z tego, że sprowadza się do , - ale nie są znane żadne redukcje z do . $A,B \in \mathsf{NP}$
$A$ $B$ $\mathsf{NPI}$
$A$ $B$
$B$ $A$

Nawet lepiej, jeśli istnieją argumenty za ich poparciem, np. Istnieją wyniki, których nie redukuje do zakładając pewne domysły w teorii złożoności lub kryptografii. $B$ $A$

Czy są jakieś naturalne przykłady takich problemów?

Przykład: domniemany jest problem izomorfizmu grafów i faktoryzacji liczb całkowitych w i istnieją argumenty potwierdzające te przypuszczenia. Czy są jakieś problemy decyzyjne trudniejsze niż te dwa, ale nie wiadomo, że są -hard? $\mathsf{NPI}$ $\mathsf{NP}$

complexity-theory np-hard Mohammad Al-Turkistany
źródło

Więc szukasz problemów takich jak z i ?

P \in N P

$P \in \mathrm{NP}$

P_{1} \leq_{p} P \leq_{p} P_{2}

$P_1 \leq_p P \leq_p P_2$

P_{1} \in N P I

$P_1 \in \mathrm{NPI}$

P_{2} \in N P C

$P_2 \in \mathrm{NPC}$

Raphael

Tak, ale nie jest znana redukcja z P do P1 (podobnie nie jest znana redukcja z P2 do P).

Mohammad Al-Turkistany,

istnieje kilka problemów ze statusem podobnym do faktoringu, patrz ten artykuł autorstwa Papadimitriou teorii. stanford.edu/~megiddo/pdf/papadimX.pdf

Marcos Villagra,

poza tym mamy bardzo ładną listę w cstheory cstheory.stackexchange.com/questions/79/…

Marcos Villagra,

dlaczego lista, do której prowadzi Marcos, nie jest odpowiedzią na twoje pytanie?

Suresh

Odpowiedzi:

Znalazłem ładny problem o nazwie ModularFactorial . Weź jako dane wejściowe dwie cyfry całkowite i , i wypisz . Ten problem jest co najmniej tak trudny jak faktoring i nie wiem, czy jest trudny dla FNP . Odniesieniem jest najnowsza (i piękna) książka Cristophera Moore'a i Stephana Mertensa The Nature of Computation , strona 79. $n$ $x$ $y$ $x! \mod y$

Marcos Villagra
źródło

Uważam, że PO szuka problemów w NP. Czy możesz przeformułować to jako problem decyzyjny?

Zach Langley,

FNP to wersja funkcji (tzn. Problemy z wyszukiwaniem) NP. W rzeczywistości faktoring nie jest w NP, to jest FNP. Na przykład problem decyzyjny dotyczący faktoringu jest trywialny, złożoność to po prostu O (1), ale problem wyszukiwania jest trudny. Ponieważ PO podał faktoring jako przykład, myślę, że jest to również poprawna odpowiedź.

Marcos Villagra,

Faktoring można przeformułować w problem decyzyjny w następujący sposób: biorąc pod uwagę liczbę całkowitą i liczbę całkowitą , czy zawiera współczynnik z ? Czy istnieje analogiczna wersja decyzyjna problemu ModularFactorial?

n

$n$

k

$k$

n

$n$

d

$d$

1 < d \leq k

$1 < d \le k$

Zach Langley,

@Marcos, Dzięki. Interesują mnie problemy decyzyjne w NP.

Mohammad Al-Turkistany,

@ZachLangley, tak, oczywiście, zgadzam się, ale myślałem w innej wersji decyzji, a mianowicie: „czy x ma czynnik?”. Odpowiedź brzmi: „tak” zawsze. Możesz zrobić to samo z modularfactorial, podać liczbę całkowitą k i zdecydować, czy jest większy niż czy nie.

x! \mod y

$x!\mod y$

k

$k$

Marcos Villagra,