Masalah alami dalam

26

Apakah ada masalah alami dalam yang tidak (diketahui / dianggap) di ? $NP \cap coNP$ $UP \cap coUP$

Jelas besar satu semua orang tahu tentang di adalah versi keputusan anjak piutang (tidak n memiliki faktor ukuran paling k), tapi itu sebenarnya di . $NP \cap coNP$ $UP \cap coUP$

cc.complexity-theory complexity-classes np Joshua Grochow
sumber

Meskipun secara teknis ini harus menjadi wiki komunitas karena saya sedang mencari daftar, saya tidak tahu APAPUN masalah seperti itu, jadi saya tidak mengharapkan lebih dari satu jawaban (dan ketika itu datang, itu layak mendapat pujian). Jika ternyata ada beberapa masalah seperti itu maka saya akan mengubahnya ke wiki komunitas.

Joshua Grochow

2

Bisakah Anda mendefinisikan UP, atau memberikan tautan.

Emil

15

Sementara game paritas diketahui berada di keduanya, diklaim bahwa game paritas stokastik tidak dikenal berada di UP intersect coUP.

Lev Reyzin
sumber

Saya menerima ini sebagai jawaban "the" karena itu satu-satunya yang tidak melibatkan masalah janji :). (Maaf Andy.) Juga, meskipun penjawab tidak memiliki cara untuk mengetahui hal ini, itulah yang saya cari sejak saya terinspirasi untuk menanyakan pertanyaan ini setelah membaca jawaban ini untuk pertanyaan yang berbeda: cstheory.stackexchange.com/questions/79/ ... (yang tentang permainan paritas).

Joshua Grochow

13

Masalah kisi adalah sumber kandidat yang baik. Diberi dasar untuk kisi dalam , orang dapat mencari vektor kisi bukan nol yang ( ) normanya paling kecil kemungkinannya; ini adalah 'Masalah Vektor Terpendek' (SVP). Juga, diberikan dasar untuk dan titik , orang dapat meminta vektor kisi sedekat mungkin ke ; ini adalah 'Masalah Vektor Paling Dekat' (CVP). $L$ $R^n$ $\ell_2$ $L$ $t \in R^n$ $t$

Kedua masalah ini sulit untuk dipecahkan. Aharonov dan Regev menunjukkan bahwa dalam (NP coNP), seseorang dapat menyelesaikannya dalam $\cap$ faktor: $O(\sqrt{n})$

http://portal.acm.org/citation.cfm?id=1089025

Saya sudah membaca makalah, dan saya pikir tidak ada petunjuk dari pekerjaan mereka bahwa seseorang dapat melakukan ini di UP coUP, apalagi UP coUP. $\cup$ $\cap$

Teknisnya: seperti yang disebutkan, ini adalah masalah pencarian, jadi sebenarnya kita harus berhati-hati tentang apa yang kita maksudkan ketika kita mengatakan bahwa mereka berada dalam kelas kompleksitas. Menggunakan varian decisional dari masalah aproksimasi, masalah keputusan kandidat yang kita dapatkan adalah masalah janji : diberi kisi , bedakan antara dua kasus berikut: $L$

Kasus I: memiliki vektor bukan nol pada norma ; $L$ $\leq 1$

Kasus II: tidak memiliki vektor non-nol dari norma $L$ $\leq C\sqrt{n}$ $C > 0$

$\cap$ $\cap$ $\setminus$ $\cap$ $\setminus$ $\neq$ $\Pi$ $L$ $\Pi$

Andy Drucker
sumber

3

Sangat menarik! Saya pikir "teknisitas" dari kelas janji sangat relevan, meskipun. Sebagai contoh, Valiant-Vazirani menunjukkan bahwa PromiseUP adalah NP-hard di bawah pengurangan acak, namun saya ragu ada hal seperti itu untuk UP. (Memang, jika VV dapat diderandomisasi dan ini benar, maka kita akan memiliki NP = UP. Tentu saja, tidak ada banyak konsekuensi buruk yang diketahui dari NP = UP, tetapi tampaknya sangat tidak mungkin.)

Joshua Grochow

1

Π

$\Pi$

Π

$\Pi$

Π

$\Pi$

7

$\cap$

Lance Fortnow
sumber

3

Lance: apakah Anda memiliki pointer untuk menunjukkan GI tidak dalam UP atau tidak dalam co-UP? Tidak jelas bagi saya bagaimana menunjukkan bahwa GI tidak dapat direduksi menjadi ruang IG menjadi terbatas pada grafik yang kaku (grafik tanpa automorfisme nontrivial); ada pengurangan Turing sederhana.

András Salamon

Saya tidak tahu konsekuensi menarik dari GI dalam UP atau dalam hal ini, GI dalam P.

Lance Fortnow

@ AndrásSalamon: Saya baru saja memperhatikan komentar Anda (dari beberapa tahun yang lalu). Saya pikir saya menjadi sangat lambat hari ini, tapi saya tidak melihat "pengurangan Turing sederhana" dari GI ke GI pada grafik yang kaku. Bisakah Anda menguraikan?

Joshua Grochow

@ JoshuaGrochow: Saya tidak yakin dengan detailnya sekarang, tapi saya pikir ini hanya referensi ke salah satu cara standar untuk menguatkan grafik, misalnya mengganti setiap sisi dengan gadget yang sesuai. Saya tidak berpikir saya bermaksud menyiratkan ini efisien .

András Salamon

Masalah alami dalam

Jawaban: