Apakah APX terkandung dalam NP?

15

Masalah P dikatakan dalam APX jika ada beberapa konstanta c> 0 sedemikian sehingga algoritma aproksimasi waktu polinom ada untuk P dengan faktor aproksimasi 1 + c.

APX berisi PTAS (terlihat hanya dengan memilih konstanta c> 0) dan P.

Apakah APX dalam NP? Secara khusus, apakah keberadaan algoritma perkiraan polinomial-waktu untuk beberapa faktor perkiraan menyiratkan bahwa masalahnya ada di NP?

cc.complexity-theory complexity-classes apx Andrew W.
sumber
Saya pikir "apa yang diketahui tentang kelas X relatif terhadap semua kelas Y lainnya" terlalu kabur sebagai pertanyaan, kecuali beberapa rincian lebih lanjut diberikan tentang jenis hubungan yang dicari.
András Salamon
Maksud saya hubungan seperti 'mengandung', 'terkandung dalam', 'tidak mengandung'.
Andrew W.
Setelah beberapa pemikiran, saya mempersempit pertanyaan ke hubungan spesifik yang paling saya minati.
Andrew W.
1
Apa sebenarnya yang dimaksud dengan bertanya apakah APX terkandung dalam NP? APX terdiri dari masalah "optimisasi NP" yang dapat diperkirakan sedangkan NP terdiri dari masalah keputusan. Selain itu, menurut definisi, versi keputusan masalah optimisasi NP ada di NP. Mungkin Anda memikirkan hal lain?
Joshua Grochow
Kamu benar Joshua. Ian menjawab pertanyaan yang seharusnya saya ajukan.
Andrew W.

Jawaban:

20

APX didefinisikan sebagai bagian dari NPO, jadi ya, jika masalah optimisasi ada di APX maka masalah keputusan terkait adalah dalam NP.

Namun, jika yang Anda tanyakan adalah apakah masalah sewenang-wenang harus dalam NP (atau NPO) jika ada waktu poli O (1) -proximation, maka jawabannya adalah tidak. Saya tidak tahu ada masalah alami yang berfungsi sebagai contoh tandingan, tetapi orang bisa mendefinisikan masalah maksimalisasi buatan di mana tujuannya adalah jumlah dari dua istilah, istilah besar yang mudah dioptimalkan dalam P, dan istilah yang jauh lebih kecil yang menambahkan sejumlah kecil jika bagian dari solusi mengkodekan jawaban untuk beberapa masalah sulit (di luar NP). Kemudian Anda dapat menemukan, katakanlah, perkiraan 2 dalam waktu poli dengan berkonsentrasi pada istilah yang mudah, tetapi menemukan solusi yang optimal akan membutuhkan pemecahan masalah yang sulit.

Ian
sumber
2
Saya menerima jawaban Anda karena menjawab pertanyaan yang saya ajukan ('Apakah APX terkandung dalam NP?') Dan pertanyaan yang seharusnya saya tanyakan ('Apakah waktu-O (1) kira-kira menyiratkan solusi tepat dalam NP?').
Andrew W.
1
Kelas luas masalah yang tidak terkandung dalam NPO dan NP tetapi memiliki pendekatan faktor konstan adalah kelas masalah online (Pertanyaan tentang kelas kompleksitas apa yang berisi masalah online ada di sini cstheory.stackexchange.com/questions/1664/… ) .
Oleksandr Bondarenko