Naturalni kandydaci do hierarchii wewnątrz NPI

22

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 .PNPNPINPPNPNPI

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.N P I N P I N P INPPNPINPINPI

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 N P I A B B AA,BNP
ABNPI
AB
BA

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.ABA

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?N PNPINP

Mohammad Al-Turkistany
źródło
1
Więc szukasz problemów takich jak z i ? P 1 p P p P 2 P 1N P I P 2N P CPNPP1pPpP2P1NPIP2NPC
Raphael
1
Tak, ale nie jest znana redukcja z P do P1 (podobnie nie jest znana redukcja z P2 do P).
Mohammad Al-Turkistany,
2
istnieje kilka problemów ze statusem podobnym do faktoringu, patrz ten artykuł autorstwa Papadimitriou teorii. stanford.edu/~megiddo/pdf/papadimX.pdf
Marcos Villagra,
8
poza tym mamy bardzo ładną listę w cstheory cstheory.stackexchange.com/questions/79/…
Marcos Villagra,
2
dlaczego lista, do której prowadzi Marcos, nie jest odpowiedzią na twoje pytanie?
Suresh

Odpowiedzi:

5

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.x ynxyx!mody

Marcos Villagra
źródło
1
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,
1
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? nknd1<dk
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!modyk
Marcos Villagra,