Hampir selalu hampir benar

11

Saya mencari kelas kompleksitas yang berhubungan dengan APX karena BPP berhubungan dengan P. Saya sudah mengajukan pertanyaan yang sama di sini , tapi mungkin TCS akan menjadi lokasi yang lebih berbuah untuk jawaban.

Alasan untuk pertanyaan ini adalah bahwa dalam masalah praktis kita sering perlu menemukan jawaban perkiraan (dengan demikian APX) dengan kepercayaan yang cukup tinggi (dengan demikian BPP), yang akan membuat kelas masalah dengan algoritma pendekatan probabilistik terbatas berpotensi menjadi model yang berguna dari apa yang dapat dihitung dalam praktek.

Calon yang mungkin dari kelas tersebut adalah : masalah yang menerima solusi yang diperkirakan dengan subrutin probabilistik terbatas; Namun, saya tidak yakin bahwa kelas seperti itu akan menjadi pengaturan yang tepat untuk perkiraan probabilitas yang dapat dihitung kelas.APXBPP

Baik BPP dan APX telah dipelajari secara luas. Apakah itu kasus untuk , atau kelas mana yang akan menjadi yang terbaik untuk menangkap masalah di atas?APXBPP

cc.complexity-theory approximation-hardness Michael
sumber
BPP dan P adalah kelas masalah keputusan. Mungkin Anda harus terlebih dahulu bertanya apa fungsi / kelas pencarian yang sesuai dengan BPP sebelum pindah ke perkiraan, saya pikir jika kita memiliki kelas fungsi / pencarian maka definisi versi aproksimasi seharusnya tidak sulit.
Kaveh
1
Saya pikir yang Anda cari adalah versi optimisasi pembelajaran PAC (Mungkin Sekitar Tepat). Sedangkan teori pembelajaran PAC secara khusus tentang (secara acak, dengan kemungkinan tinggi kebenaran) fungsi pembelajaran untuk menggambarkan data, seperti dalam pembelajaran mesin, Anda bertanya tentang masalah optimisasi. Meski begitu, mungkin literatur pembelajaran PAC adalah tempat yang baik untuk mulai mencari ...
Joshua Grochow
3
Daripada notasi oracle, apa yang Anda gambarkan lebih dekat dengan operator BP. Operator BP didefinisikan pada kelas kompleksitas masalah keputusan. Seharusnya mudah untuk memperluas definisi untuk menjanjikan masalah dan mendefinisikan versi masalah janji dari kelas kompleksitas Anda dengan cara itu. Menentukan versi untuk masalah pengoptimalan mungkin lebih sulit.
Sasho Nikolov

Jawaban:

1

Untuk setiap fungsi objektif yang diberikan, biarkan BotL (best-of-the-list) menjadi algoritma yang mengevaluasi fungsi objektif pada set input dan mengembalikan input dari daftar yang memiliki output maksimal (dari antara input tersebut), dengan ikatan rusak sewenang-wenang. Karena APX hanya mencakup masalah
yang fungsi objektifnya dapat dihitung dalam waktu polinomial deterministik, BotL dapat diimplementasikan secara deterministik dalam waktu polinomial.Selain itu, nilai yang dikembalikan oleh BotL
setidaknya sama baiknya dengan input di setidaknya BotL dievaluasi pada.Khususnya,
jika salah satu input dalam daftar itu cukup baik maka output BotL akan cukup baik.
Oleh karena itu menjalankan BotL pada output dari sejumlah besar eksekusi independen dari algoritma basis dapat memperkuat probabilitas keberhasilan dari 1 / poli menjadi 1- (1 / (2 ^ poli)).

Sebagai konsekuensi dari paragraf sebelumnya,
tingkat kepercayaan yang tepat pada dasarnya tidak mempengaruhi kelas yang dihasilkan.
(Situasi ini sangat analog dengan RP .)

Saya tidak dapat menemukan apa pun tentang itu di kebun binatang kompleksitas, meskipun
mungkin ada pembicaraan tentang hal itu diberikan di bengkel yang dimaksud dalam makalah ini .


sumber
1
OP menanyakan nama kelas masalah yang memiliki algoritma aproksimasi faktor konstan acak. Anda mengatakan (saya pikir) bahwa probabilitas keberhasilan untuk algoritma seperti itu dapat diperkuat. Saya gagal melihat bagaimana ini menjawab pertanyaan?
Sasho Nikolov
Saya tidak melihat pertanyaan itu di OP. Michael bertanya apakah kelas telah "dipelajari secara luas". Memang, saya tidak banyak bicara tentang itu, tetapi saya (setidaknya mencoba) mengatasi kesalahpahaman tentang seperti apa kelas itu nantinya.
Tidak ada kesalahpahaman dalam pertanyaan itu.
Sasho Nikolov
Baik. Kesalahpahaman itu ada dalam "Calon yang mungkin dari kelas semacam itu adalah ... kemungkinan yang dapat dihitung secara probabilistik." paragraf, yang ada di pos tetapi bukan pertanyaan.
1
Dengan klarifikasi, masih pendapat saya bahwa jawaban Anda tidak memperbaiki kesalahpahaman dalam OP, tetapi hanya memberikan fakta sewenang-wenang tentang perkiraan acak.
Sasho Nikolov