Kandidat alami untuk hierarki di dalam NPI

Mari kita berasumsi bahwa . N P I adalah kelas masalah dalam N P yang tidak dalam P atau dalam N P -hard. Anda dapat menemukan daftar masalah yang diduga sebagai N P I di sini .$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$$\mathsf{NPI}$

Teorema Ladner memberitahu kita bahwa jika maka ada hierarki tak terbatas dari masalah N P I , yaitu ada masalah N P I yang lebih sulit daripada masalah N P I lainnya.$\mathsf{NP}\neq\mathsf{P}$$\mathsf{NPI}$$\mathsf{NPI}$$\mathsf{NPI}$

Saya mencari kandidat dari masalah seperti itu, yaitu saya tertarik pada pasangan masalah
- , - A dan B yang diduga sebagai N P I , - A diketahui mereduksi menjadi B , - tetapi ada tidak ada pengurangan yang diketahui dari B ke $A,B \in \mathsf{NP}$
$A$$B$$\mathsf{NPI}$
$A$$B$
$B$$A$ .

Bahkan lebih baik jika ada argumen untuk mendukung ini, misalnya ada hasil yang tidak mengurangi menjadi $B$$A$ dengan asumsi beberapa dugaan dalam teori kompleksitas atau kriptografi.

Apakah ada contoh alami dari masalah seperti itu?

Contoh: masalah Grafik isomorfisma dan masalah Integer Faktorisasi yang menduga berada di dan ada argumen yang mendukung dugaan ini. Apakah ada masalah keputusan yang lebih sulit daripada keduanya tetapi tidak diketahui sebagai N P -hard?$\mathsf{NPI}$$\mathsf{NP}$

Isomorfisme Kelompok Grafik Isomorfisme ≤ m Cincin Isomorfisme. Factor Integer Juga ≤ m Ring Isomorphism [ Kayal dan Saxena ]. Juga Grafik Automorfisme ≤ $\leq_m$$\leq_m$$\leq_m$$\leq_m$ Graph Isomorphism.

Tidak hanya ada pengurangan tidak dikenal dengan cara lain, tapi ada provably ada -reduction dari Grafik Iso ke Grup Iso [ Chattopadhyay, Toran, dan Wagner ].$\mathsf{AC}^0$

Perhatikan bahwa reduksi dari Ring Isomorphism ke Graph Isomorphism juga akan memberikan pengurangan dari Integer Factoring ke Graph Isomorphism. Bagi saya, pengurangan seperti itu akan mengejutkan meskipun mungkin tidak mengejutkan.

(Untuk Graph Automorphism vs Graph Isomorphism, versi penghitungannya diketahui setara satu sama lain dan setara dengan menentukan Graph Isomorphism. Namun, itu tidak selalu berarti banyak, karena versi penghitungan pencocokan bipartit setara dengan versi penghitungan SAT. )

Saya tidak berpikir ada konsensus yang nyata untuk yang, jika ada, ini benar-benar dalam . Jika salah satu dari masalah ini adalah N P -complete maka P H runtuh ke tingkat kedua. Jika anjak piutang adalah N P -Lengkap, maka runtuh ke tingkat pertama, yaitu N P = c o N P .$\mathsf{P}$$\mathsf{NP}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{NP} = \mathsf{coNP}$

Juga, saya ingat bahwa menggunakan teknik yang mirip dengan Ladner seseorang dapat menunjukkan bahwa setiap pemesanan parsial yang dapat dihitung dapat tertanam dalam pemesanan pada masalah dalam N P (jadi itu bukan hanya hierarki, tetapi urutan parsial yang dapat dihitung secara sewenang-wenang rumit) .$\leq_{m}$$\mathsf{NP}$