cc.complexity-theory – Pregunta simple sobre problemas de decisión.

Pregunta:

(Estoy en medio de mi primer curso teórico de cs, así que me disculpo de antemano por lo que probablemente sea una pregunta estúpida).

Entonces, decimos que algún lenguaje L está en P, lo que significa que se puede construir una máquina de Turing que da como resultado un 1 si x está en L y 0 en caso contrario; además, la máquina funciona en tiempo polinomial. Entiendo esto.

Pero mucha gente dice que hay ciertos problemas en P que no me parecen problemas de decisión; por ejemplo, maximizar una función sujeta a restricciones lineales. ¿Qué significa que la "programación lineal" está en P? ¿Seguramente "encontrar el valor máximo" no es un problema de decisión?

Respuesta:

Tienes razón: formalmente P incluye solo problemas de decisión. Pero muchos problemas de decisión tienen problemas de optimización correspondientes: encuentre el tamaño de la mayor coincidencia en un gráfico, encuentre la longitud de la ruta más corta de sa t en un gráfico, etc.

A menudo, estos pueden reducirse a problemas de decisión preguntando en su lugar: "¿Tiene la gráfica una coincidencia que utilice más de k aristas?" o "¿Hay una ruta s-> t de longitud menor que k?"

Obviamente, si puede resolver el problema de optimización, puede resolver el problema de decisión. Lo contrario también suele ser cierto, hasta factores logarítmicos. Si desea saber el tamaño de la coincidencia más grande en un gráfico, por ejemplo, puede realizar llamadas repetidas a su algoritmo para el problema de decisión "¿Tiene la gráfica una coincidencia utilizando más de k bordes?" y haga una búsqueda binaria en el valor "k". De esta forma, necesitará como máximo las llamadas log (m), donde m es el número de aristas. Para la mayoría de los problemas existe una reducción análoga.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım