Kelas kompleksitas yang terkait dengan pencarian lengkap

14

Apa kelas kompleksitas yang terkait dengan algoritma pencarian lengkap? (jika ada)

Apakah NP atau PSPACE?

Apakah ada model komputasi terbatas yang menangkap kelas algoritma pencarian lengkap mirip dengan model untuk pemrograman serakah dan dinamis?

cc.complexity-theory ds.algorithms reference-request big-picture machine-models Anonim
sumber
6
Lebih tepat untuk cs.stackexchange.
Yuval Filmus
2
Bagaimana dengan E atau EXP?
Yuval Filmus
5
@YuvalFilmus benar-benar? Ini sepertinya pertanyaan yang menarik bagi saya dan tidak sepele sama sekali
Suresh Venkat
1
Berbagai kelas pencarian lokal dimulai dengan ruang masalah di mana solusi dijamin ada, dan tantangannya adalah untuk mencari ruang dalam waktu subeksponensial. Mungkin terkait.
Suresh Venkat
5
Agak kabur tapi saya suka pertanyaannya. Saya menulis makalah tentang itu sejak lama. Mungkin ini akan membantu penanya Anonim: stanford.edu/~rrwill/bfsearch-rev.ps [PERINGATAN: Kemungkinan saya tidak setuju dengan hampir semua pendapat yang dinyatakan di sana, ditulis 10 tahun lalu]
Ryan Williams

Jawaban:

21

Agak kabur, tapi saya suka pertanyaannya. Saya menulis makalah tentang itu PANJANG yang lalu. Mungkin ini akan membantu penanya Anonim:

Pencarian Brute Force dan Komputasi Berbasis Oracle

PNP3PSPACE

[ PERINGATAN PERINGATAN PERINGATAN: Kemungkinan saya tidak setuju dengan hampir semua pendapat yang tercantum dalam makalah ini. Itu ditulis sekitar 10 tahun yang lalu, oleh seseorang dengan nama yang sama tetapi yang pada dasarnya adalah orang yang berbeda. ]

Ryan Williams
sumber
2
Cinta peringatannya! :)
Tayfun Pay