Kekerasan perkiraan dengan asumsi NP! = CoNP

Dua asumsi umum untuk membuktikan kekerasan hasil perkiraan adalah dan Unique Games Conjecture. Apakah ada kekerasan hasil perkiraan dengan asumsi NP \ neq coNP ? Saya mencari masalah A sehingga "sulit untuk memperkirakan A dalam faktor \ alpha kecuali NP = coNP ".$P \neq NP$$NP \neq coNP$$A$$A$$\alpha$$NP = coNP$

Diketahui bahwa "menunjukkan faktor $n$ kekerasan NP untuk masalah vektor terpendek akan menyiratkan bahwa $NP = coNP$ ". Perhatikan bahwa ini adalah "kebalikan" dari apa yang saya cari.

Klarifikasi: Ada kemungkinan bahwa $NP=coNP$ dan masih pertanyaan P vs NP terbuka. Saya mencari kekerasan hasil perkiraan yang akan menjadi salah jika $NP=coNP$ tetapi tidak terpengaruh (yaitu, masih tetap sebagai dugaan) oleh $P \neq NP$ .

Berikut ini pengamatan langsung. Jika Anda mengasumsikan $NP \neq coNP$ , maka cukup mudah untuk melihat ada masalah optimasi $NP$ yang bahkan tidak memiliki algoritma aproksimasi nondeterministik yang baik , dalam beberapa hal.

Misalnya, teorema PCP mengatakan bahwa Anda dapat menerjemahkan SAT ke dalam masalah membedakan apakah dari klausa terpenuhi dan semua klausa terpenuhi, untuk beberapa . Misalkan ada algoritma nondeterministic yang dapat membedakan antara dua kasus ini, dalam arti bahwa algoritma nondeterministic dapat melaporkan di setiap jalur perhitungan baik "semua puas" atau "paling banyak ", dan dikatakan "paling banyak "di beberapa lintasan jika paling banyak dapat dipenuhi, jika tidak dikatakan" semua puas "di setiap lintasan perhitungan jika semua persamaan dapat dipenuhi. Ini cukup untuk memutuskan SAT di ,$1-\varepsilon$$\varepsilon > 0$$1-\varepsilon$$1-\varepsilon$$1-\varepsilon$$coNP$$NP=coNP$. Tampak jelas bahwa keberadaan algoritma nondeterministic semacam itu tidak berpengaruh pada apakah .$P = NP$

Sangat masuk akal bahwa ada skenario yang lebih "alami": masalah optimasi yang sulit diperkirakan dalam waktu polinomial deterministik di bawah tetapi tidak diketahui sulit di bawah . (Ini mungkin yang benar-benar ingin Anda tanyakan.) Banyak kekerasan hasil perkiraan pertama-tama dibuktikan dengan beberapa asumsi yang lebih kuat (mis. tidak dalam waktu subeksponensial, atau tidak dalam ). Dalam beberapa kasus, perbaikan selanjutnya melemahkan asumsi yang diperlukan, kadang-kadang turun ke . Jadi ada harapan bahwa ada jawaban yang sedikit lebih memuaskan untuk pertanyaan Anda daripada yang ini. Sulit untuk bertanya-tanya bagaimana mungkin ada masalah itu$NP \neq coNP$$P \neq NP$$NP$$NP$$BPP$$P \neq NP$tidak dapat dibuktikan sulit untuk diperkirakan dalam polytime deterministik di bawah , tetapi dapat dibuktikan sulit di bawah . Itu berarti bahwa memberi tahu kita sesuatu tentang perhitungan deterministik yang belum dikatakan ; secara intuitif, ini sulit untuk dipahami.$P \neq NP$$NP \neq coNP$$NP \neq coNP$$P \neq NP$

Penafian: ini bukan jawaban langsung.

Sebenarnya ada lebih banyak kondisi kekerasan selain P! = NP dan UGC. David Johnson menulis kolom yang indah untuk Transaction on Algorithms pada tahun 2006 tentang masalah ini. Dia mencantumkan berbagai asumsi berbeda yang digunakan untuk menunjukkan kekerasan, dan bagaimana mereka saling berhubungan.

Sayangnya, ini semua adalah NP vs kelas deterministik (dengan pengecualian NP dan co-AM). NP vs co-NP tidak tercakup sama sekali.

$NP \ne coNP$ adalah hipotesis yang lebih kuat daripada karena menyiratkan . Jadi, setiap kekerasan hasil perkiraan dengan asumsi juga akan mengikuti dari asumsi .$P \ne NP$$NP\ne coNP$$P\ne NP$$P\ne NP$$NP\ne coNP$

Ini bukan jawaban langsung

Masalah k-Choosability adalah -complete. Di bawah asumsi bahwa , k-Choosability benar-benar lebih sulit daripada k-Coloring pada grafik umum. Oleh karena itu, kira-kira angka kromatik daftar lebih sulit daripada angka kromatik. Diketahui bahwa pewarnaan k adalah sepele untuk grafik bipartit. Namun, menentukan daftar nomor kromatik grafik bipartit adalah -hard. (Bahkan 3-Pilihan adalah -lengkap)$\prod_2^P$$NP \ne coNP$$NP$$\prod_2^P$

Noga Alon, Pewarnaan terbatas pada grafik