Clase de complejidad asociada a la búsqueda exhaustiva.

14

¿Cuál es la clase de complejidad asociada con los algoritmos de búsqueda exhaustiva? (si hay uno)

¿Es NP o PSPACE?

¿Existen modelos restringidos de cómputo que capturen la clase de algoritmos de búsqueda exhaustiva similares a los modelos para programación codiciosa y dinámica?

cc.complexity-theory ds.algorithms reference-request big-picture machine-models Anónimo
fuente
66
Más apropiado para cs.stackexchange.
Yuval Filmus el
2
¿Qué tal E o EXP?
Yuval Filmus el
55
@YuvalFilmus realmente? Esto me parece una pregunta interesante y nada trivial
Suresh Venkat
1
Las diversas clases de búsqueda locales comienzan con un espacio problemático donde se garantiza que existe una solución, y el desafío es buscar el espacio en tiempo subexponencial. Puede estar relacionado.
Suresh Venkat
55
Es un poco vago pero me gusta la pregunta. Escribí un artículo al respecto hace mucho tiempo. Tal vez esto ayude al interlocutor anónimo: stanford.edu/~rrwill/bfsearch-rev.ps [ADVERTENCIA: es probable que no esté de acuerdo con casi todas las opiniones allí, fue escrito hace 10 años]
Ryan Williams

Respuestas:

21

Es un poco vago, pero me gusta la pregunta. Escribí un artículo al respecto hace mucho tiempo. Quizás esto ayude al interlocutor anónimo:

Búsqueda de fuerza bruta y computación basada en Oracle

Aquí hay un resumen. De manera informal, si usted no mantiene ningún trabajo al rayado de los ensayos anteriores, y sólo tratar todas las posibles soluciones en orden lexicográfico hasta que se encuentre una solución deseada, entonces la fuerza bruta corresponde precisamente a . Si mantiene alrededor de 3 bits de trabajo desde cero de una posible solución a la siguiente, puede hacer P S P A C E , a través del teorema de Barrington. Hay otras posibilidades, como lo que sucede cuando no se ejecuta en orden lex pero de acuerdo con alguna otra lista eficientemente computable de todas las cadenas.PAGnortePAG3PAGSPAGUNCmi

[ ADVERTENCIA ADVERTENCIA ADVERTENCIA: es probable que no esté de acuerdo con casi todas las opiniones expresadas en este documento. Fue escrito hace unos 10 años, por alguien con el mismo nombre pero que es esencialmente una persona diferente. ]

Ryan Williams
fuente
2
Me encanta la advertencia! :)
Tayfun paga el