Naturalni kandydaci do hierarchii wewnątrz NPI

16

Załóżmy, że . N P ja to klasa problemów w N P , które nie są ani w P ani w N P -hard. Listę problemów, które można przypuszczać, że są N P I tutaj .P≠NPNPINPPNPNPI

Twierdzenie Ladnera mówi nam, że jeśli to istnieje nieskończona hierarchia problemów N P I , tzn. Są problemy N P I , które są trudniejsze niż inne problemy N P I.NP≠PNPINPINPI

Szukam kandydatów takich problemów, tj Jestem zainteresowany par problemów
- , - i B są Przypuszcza się N P I , - znany jest zmniejszenie do B , - ale istnieją nie wiadomo, redukcje z B do A .A,B∈NP
ABNPI
AB
BA

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

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

Przykład: domniemano, że problem izomorfizmu grafu i problem faktoryzacji liczb całkowitych występuje w i istnieją argumenty potwierdzające te przypuszczenia. Czy są jakieś problemy decyzyjne twardsze niż te dwa, ale nie wiadomo, aby mieć N P -hard?NPINP

cc.complexity-theory np-hardness np-intermediate Mohammad Al-Turkistany
źródło
3
Wysłany tutaj na podstawie sugestii Kaveha po wygraniu nagrody CS Stackexchange bez zadowalającej odpowiedzi.
Mohammad Al-Turkistany
Kopiuj na temat informatyki .
Kaveh

Odpowiedzi:

18

Grupowy izomorfizm Wykres Izomorfizm ≤ m Izomorfizm pierścieniowy. Również faktoring całkowity ≤ m Izomorfizm pierścieniowy [ Kayal i Saxena ]. Również automorfizm grafów ≤ m Izomorfizm grafów.≤m≤m≤m≤m

Nie tylko nie ma znanych redukcji w drugą stronę, ale możliwe jest, że nie ma redukcji z Graph Iso do Group Iso [ Chattopadhyay, Toran i Wagner ].AC0

Należy zauważyć, że redukcja z izomorfizmu pierścieniowego do izomorfizmu graficznego zapewniłaby również redukcję z faktoringu liczb całkowitych do izomorfizmu grafowego. Dla mnie taka redukcja byłaby zaskakująca, ale może nie szokująca.

(W przypadku Graph Automorphism vs. Graph Isomorphism, ich wersje zliczające są znane jako równoważne sobie nawzajem i równoważne z decydowaniem o izomorfizmie grafowym. Jednak to niekoniecznie wiele mówi, ponieważ licząca wersja dopasowania dwustronnego jest równoważna z policzoną wersją SAT. )

Nie sądzę, że istnieje realne konsensus, co do których, jeśli w ogóle, to są rzeczywiście w . Jeśli którykolwiek z tych problemów jest N P -Complete następnie P H opada do drugiego poziomu. Jeśli faktoringowa N P -Complete, następnie opada do pierwszego stopnia, to jest N P = c o N P .PNPPHNPNP=coNP

Wydaje mi się też, że przy użyciu technik podobnych do Ladnera można wykazać, że dowolne policzalne częściowe uporządkowanie może być osadzone w porządku na problemach w N≤m (tak, to nie tylko hierarchia, ale dowolnie skomplikowane policzalny porządek częściowy) .NP

Joshua Grochow
źródło
1
Uważam, że ciche mieszanie wersji liczących i wersji decyzyjnych jest dość mylące. Pierścień jest strukturą skończoną, a izomorfizm struktur skończonych (wersja decyzyjna) jest kompletny pod względem GI. Tak więc wersja decyzyjna izomorfizmu pierścieniowego nie jest ani trudniejsza niż GI, ani trudniejsza niż faktoring całkowity.
Thomas Klimpel
1
@ThomasKlimpel: Tylko b / c iso struktur skończonych jest GI-zupełne, nie oznacza, że ​​dla jakiejkolwiek konkretnej klasy struktur skończonych, problemem iso jest GI-zupełna. Mianowicie. grupa ISO nie jest znana ani nie jest uważana za kompletną GI. Jest mało prawdopodobne, aby pierścieniowe izo, gdy podano je w tabelach dodawania / wielu, jest pełne GI, biorąc pod uwagę, że jest w . Wersja RingIso, do której się odwołuję w powyższej odpowiedzi, jest wersją podaną przez geny i relacje. TIME(O(nlog⁡n))
Joshua Grochow
@ThomasKlimpel: Jeśli przez „ciche miksowanie” odwołujesz się do akapitu w nawiasie, wspomniane tam równoważności dotyczą terminów wielomianowych redukcji Turinga ( zwanych również redukcjami Cooka), a nie redukcji wielokrotnych jeden.
Joshua Grochow
OK, przeczytałem teraz początek odniesienia. Pierścień jest podany w tabelach add / mult, ale mają one kanoniczną reprezentację skompresowaną dla pierścieni (ponieważ grupa addytywna jest abelowa), więc wynik kompletności GI dla struktur skończonych nie jest istotny. Nie scharakteryzowałbym tej reprezentacji jako „genów i relacji”, ponieważ brzmi to jak „ciche miksowanie”, na które początkowo narzekałem. Uwaga niezwiązana: ani nie odniosłem się do akapitu w nawiasie, ani nie zakładałem, że izomorfizm pierścieniowy powinien być kompletny do przewodu pokarmowego, tylko że nie powinien być trudniejszy niż przewód pokarmowy.
Thomas Klimpel
@ThomasKlimpel: Przepraszam, masz rację, to nie całkiem geny i relacje. (I źle odczytałem twoją uwagę na temat GI-complete vs „nie trudniej niż GI”). Myślałem, że rozumiem, co masz na myśli przez „ciche miksowanie”, ale biorąc pod uwagę twój ostatni komentarz, już nie rozumiem. Być może nie jest to jednak tak istotne dla cstheory.stackexchange i możesz wysłać mi e-mail bezpośrednio, aby wyjaśnić moje zrozumienie (po czym mogę w razie potrzeby zaktualizować odpowiedź).
Joshua Grochow