¿Existen problemas sin algoritmos eficientes, donde los teoremas de existencia han demostrado que tales algoritmos deben existir?

22

¿Hay problemas en CS donde no se conocen algoritmos eficientes, a pesar de los teoremas de existencia que demuestran que tales algoritmos eficientes deben existir?

¿Cómo se llaman estos problemas? ¿Dónde puedo encontrar más?

ds.algorithms reference-request terminology z5h
fuente
44
Creo que esto es relevante: en.wikipedia.org/wiki/Minor_(graph_theory)#Algorithms
Philip White
3
¿Cuál es tu pregunta? En el título dice "soluciones", pero en los contenidos escribes "algoritmos".
Marcos Villagra
66
Creo que sería mejor si pides problemas interesantes / naturales , de lo contrario es fácil definir tales problemas: toma cualquier enunciado matemático que no se sepa que es verdadero o falso, haz que el problema salga 1 (independiente de la entrada) si es verdadero y 0 si es falso. Hay dos algoritmos muy simples que uno de ellos resuelve este problema, pero decidir cuál es básicamente probar / refutar el enunciado matemático, por lo que no sabemos cuál lo resuelve.
Kaveh

Respuestas:

9

Como ejemplo, Shelby Kimmel utiliza el método adversario en este documento para mostrar que tiene que existir el algoritmo de consulta para un determinado problema para el que no conocemos una solución de consulta constante. Ella hace esto de una manera particularmente hábil al encontrar la complejidad de la consulta del problema compuesto consigo mismo d veces y luego encuentra la complejidad de la consulta Q de la función compuesta, y observa que la complejidad de la consulta de la función original es el orden Q 1O(1)reQ .Q1re

Artem Kaznatcheev
fuente
12

Claro, hay muchos ejemplos, al menos en el espíritu de su pregunta.

A menudo uno obtiene ese resultado del método probabilístico . Por ejemplo, un artículo que me gusta que se encuentra con el problema es en la reconstrucción de gráficos en el modelo aditivo . Aquí, los autores muestran que existe un conjunto de consultas que (óptimamente) aprenderán el gráfico objetivo. Dado este conjunto, el algoritmo es eficiente. Sin embargo, utilizan el método probabilístico para mostrar la existencia de este pequeño conjunto (para cada tamaño de problema) que funcionará en todas las entradas, pero no lo construyen explícitamente. Entonces, lo mejor que pueden hacer es solo una búsqueda de fuerza bruta a través de una familia exponencial de consultas porque no tienen una construcción explícita.O(renorte)

Lev Reyzin
fuente
2

No, siempre puede usar el algoritmo más rápido y más corto para todos los problemas bien definidos . ;)

Marcus Ritt
fuente
No hablaba totalmente en serio, pero observe que la construcción de Hutter realmente prueba la corrección del algoritmo. ¿Por qué crees que no responde la pregunta?
Marcus Ritt
44
@Ross Snider: por supuesto, los lenguajes indecidibles escapan del resultado de Hutter: después de todo, ¡él está dando un algoritmo! Sin embargo, a diferencia de la búsqueda de Levin, que requiere que las instancias problemáticas tengan certificados verificables (como los problemas de búsqueda de NP), la búsqueda de Hutter no. Simplemente requiere que el problema se exprese en un lenguaje formal, que puede servir como base para buscar pruebas exhaustivamente [que algunas TM están de hecho resolviendo el problema especificado]. Además, Hutter / Levin no nos proporciona pruebas de existencia de algoritmos eficientes para un problema a menos que ya sepamos que el problema tiene dicho algoritmo.
Joshua Grochow
1
@Joshua Saqué los idiomas indecidibles como ejemplo de algo que la búsqueda de Hutter / Levin no podría decidir (traté de elegir algo obvio) pero que permanece "bien definido"; Es un argumento en contra de la reclamación en el título del artículo. Por supuesto, tuve cuidado de admitir que no había leído el contenido, lo que tendré que hacer ahora.
Ross Snider
1
¿Es este algoritmo el contenido computacional de la equivalencia de las matemáticas constructivas y clásicas en todas las declaraciones existentes?
Neel Krishnaswami
1
@Neel Kirshnaswami: ¡Es difícil de decir, ya que no sabía que existía tal equivalencia! ¿Puedes dar un puntero?
Joshua Grochow
1

Editar: La respuesta a continuación es registrar la existencia de soluciones a un problema computacional dado, no la existencia de algoritmos. Inicialmente, interpreté mal la pregunta.

Responder

Hay una clase de complejidad que captura este tipo de problemas computacionales. Es conocido como TFNP . Se definió en este documento:

Nimrod Megiddo y Christos Papadimitriou. Sobre funciones totales, teoremas de existencia y complejidad computacional . Informática teórica 81 (2): 317-324.

Aquí encontrará problemas como el Triángulo tricromático, para el cual la existencia de una solución está garantizada por el Lema de Sperner (consulte el documento para la definición de este problema).

También tienes el siguiente documento:

Christos Papadimitriou. Sobre la complejidad del argumento de paridad y otras pruebas ineficaces de existencia . Journal of Computer and Systems Science 48 (3), 1990.

En este artículo encontrarás:

  • norte
  • Equilibrio de juegos de 2 jugadores.
  • Encuentra un segundo camino hamiltoniano en un gráfico.

El documento tiene muchos ejemplos de este tipo de problemas. Así que recomiendo echarle un vistazo.

Marcos Villagra
fuente
2
La pregunta no se refiere a problemas con soluciones probables existentes para sus versiones de decisión, sino a problemas con la existencia comprobada de algoritmos eficientes. Estas son cosas diferentes. Estoy de acuerdo en que a primera vista el título puede inducir a error. Sin embargo, solo a primera vista.
Oleksandr Bondarenko
Sí, yo también estoy de acuerdo. Pero la pregunta me engañó totalmente. Ahora en este caso, la respuesta es engañosa. ¿Qué debo hacer? ¿Elimino de question? ¿O editar y poner una advertencia sobre lo que está respondiendo exactamente?
Marcos Villagra
No existen políticas para eliminar respuestas, siempre puede hacer lo que considere apropiado. Personalmente, creo que está bien dejar tu respuesta aquí. Puede hacer una declaración sobre qué pregunta está respondiendo exactamente.
Hsien-Chih Chang 張顯 之