¿Cuál es el problema abierto más antiguo en TCS?

36

Este problema está inspirado en esta pregunta de MO , que me pareció muy interesante.

¿Cuál es el problema abierto más antiguo en TCS?

Claramente esta pregunta necesita alguna aclaración.

Primero, ¿qué es TCS? Creo que la existencia de números perfectos impares no es TCS. Yo diría que el décimo problema de Hilbert es TCS. Creo que problemas como "¿Podemos construir X con una regla y una brújula" también son TCS, ya que están pidiendo un algoritmo en un modelo restringido de cómputo. Puede que no haya una forma rigurosa de definir qué es un problema de TCS, pero use su criterio. Tal vez una prueba es "Si esto se resuelve, ¿lo más probable es que aparezca en STOC / FOCS? ¿El investigador que lo resolvió probablemente sería un informático teórico?"

En segundo lugar, ¿qué es "más viejo"? Me refiero a mayor por fecha. La fecha indicada también debe ser verificable, pero no creo que esto sea demasiado difícil.

Tercero, ¿qué es un "problema abierto"? Por "problema abierto", me refiero a un problema que se consideró específicamente abierto en algún momento. Tal vez apareció al final de un artículo en la sección de problemas abiertos, o tal vez hay evidencia de que algunas personas trabajaron en él y fallaron, o tal vez hay pruebas incorrectas en la literatura, lo que sugiere que se ha estudiado. Un ejemplo de algo que no se ajusta a este criterio: "Los griegos estudiaron los objetos X e Y. Z es claramente un objeto intermedio, seguramente se preguntaron si se puede construir". Si no hay literatura sobre Z de ese período de tiempo, entonces no es un problema abierto de ese período de tiempo.

Cuarto, ¿qué quiero decir con "problema"? Me refiero a una pregunta específica de "sí / no", y no a algo como "Caracterizar todos los objetos X con la propiedad Y", porque estas preguntas a menudo no tienen una respuesta satisfactoria. Muy a menudo habrá desacuerdo sobre si la pregunta se ha resuelto. No entremos en tales preguntas aquí. Si no es una pregunta de sí / no, pero está claro que está realmente abierta, también está bien. (En caso de que esto no esté claro, por "problema" me refiero a un problema formalmente declarado. Por favor, no convierta alguna leyenda popular sobre el juego en el siglo XVI en una pregunta sobre BPP y PSPACE).

Por último, dado que esta no es una pregunta de la lista grande, publique una respuesta solo si cree que es anterior a las respuestas ya publicadas (o si cree que las respuestas publicadas no satisfacen alguna otra condición, como si no fueran TCS, o no están abiertos). Esta no es una colección indiscriminada de viejos problemas abiertos.

Robin Kothari
fuente
13
"¿Cuál es la mejor manera de cocinar carne?" Bajo un modelo de cómputo de fogata, ¿cuál es el mejor algoritmo para preparar alimentos? - relevante hace miles de años, ¡aún relevante ahora! Además, ¡hay mucha literatura sobre el problema! (Lo siento, no pude resistirme ;-))
Daniel Apon
3
¿Hay un dios? Podría ser un problema de TCS si puede ser resuelto por computadoras.
Sariel Har-Peled
99
@Daniel, '¡cuál es la mejor manera de cortar un pastel' es una pregunta real de TCS!
Suresh Venkat
3
#offtopic: es bueno ver que supercooldave ahora tiene un nombre :)
Suresh Venkat
55
Encontré un libro titulado "Una historia de algoritmos: del guijarro al microchip" ( amazon.com/dp/3540633693 ). Puede ser útil para encontrar un historial decente en algoritmos (nuevos y antiguos).
MS Dousti

Respuestas:

38

¿Cuál es la complejidad computacional de la multiplicación entera? Podría decirse que esta pregunta se remonta al menos al algoritmo de `` duplicación y mediación '' para la multiplicación de enteros descrito en el Papiro matemático Rhind, que se escribió alrededor de 1650 a . C. , pero afirma ser una copia de un documento significativamente más antiguo.

Es cierto que el papiro Rhind no consideró explícitamente la complejidad de su algoritmo. Entonces, tal vez una mejor respuesta es ¿Cuál es la complejidad de resolver sistemas de ecuaciones lineales? La investigación de algoritmos eficientes para resolver sistemas lineales se remonta al menos al comentario de Liu Hui, publicado en 263 dC , sobre Los nueve capítulos sobre el arte matemático . Específicamente, Liu Hui compara dos variantes de lo que ahora se reconoce como eliminación gaussiana, y cuenta el número de operaciones aritméticas utilizadas por cada uno, con el objetivo explícito de encontrar el método más eficiente.

Ambas preguntas siguen siendo objetivos de investigación activa.

Jeffε
fuente
99
A diferencia de Robin, no creo que sea razonable insistir en que la pregunta se haya planteado en su forma moderna. Eso es como mantener pruebas históricas de los estándares contemporáneos de rigor. Según ese estándar, la geometría axiomática comenzó con Klein, y Euclides era solo un tipo griego que saludaba con la mano.
Jeffε
66
"Según los estándares modernos de rigor, Euclides era solo un tipo griego que agitaba las manos": ese es mi próximo .sig :)
Suresh Venkat
2
Creo que tales ejemplos están bien. Lo que quería evitar es lo que sucedió en el desbordamiento matemático: hubo una discusión sobre si los griegos consideraron algún problema solo porque habían estudiado algún problema relacionado. La otra cosa que quiero evitar es preguntas filosóficas como "¿Es el universo determinista" convertido en el problema P versus BPP. Has dado un problema específico que fue considerado como un problema de cómputo por las personas que lo plantearon, y eso es perfectamente aceptable.
Robin Kothari
Esta pregunta se ha resuelto parcialmente para la multiplicación de enteros en línea. arxiv.org/abs/1101.0768
felix
23

La búsqueda de un algoritmo eficiente para factorizar parece remontarse al menos a Gauss. El artículo 329 de Disquitiones Arithmeticae de Gauss (1801) tenía la siguiente cita ( fuente ):

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length. ... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.

Por supuesto, es cierto que Gauss no definió formalmente exactamente lo que deseaba del algoritmo de factorización. Sin embargo, habló en el mismo artículo sobre el hecho de que todos los algoritmos de prueba de primalidad conocidos en ese momento eran muy "laboriosos y prolíficos".

arnab
fuente
2
Muy buena cita. ¡Es genial cómo Gauss dejó en claro que los algoritmos de factorización actuales eran "laboriosos y prolíficos"!
Robin Kothari
10

Lo siguiente, citado de

  • Goldwasser, S. y Micali, S. 1982. Cifrado probabilístico y cómo jugar al póker mental manteniendo en secreto toda la información parcial. En Actas del Decimocuarto Simposio Anual de ACM sobre Teoría de la Computación (San Francisco, California, Estados Unidos, 05 al 07 de mayo de 1982). STOC '82. ACM, Nueva York, NY, 365-377. DOI = http://doi.acm.org/10.1145/800070.802212

Se refiere a otro problema que se remonta a Disquitiones Arithmeticae de Gauss (1801):

(qN)=1(qN)

PD: Por ahora, conocemos dos de los cuatro problemas algorítmicos :

  1. Factoring (como lo menciona arnab);
  2. Decidir la residousidad cuadrática.

¿Cuáles son los dos problemas restantes descritos por Gauss?

MS Dousti
fuente
9

En la literatura de nuestro país, hay un dicho que traduzco literalmente como "El enigma se vuelve fácil cuando se resuelve". Aunque no es una buena traducción, se refiere al hecho de que cuando tiene la solución, puede verificarla fácilmente; Sin embargo, antes de eso, el acertijo parece muy difícil.

Esto se refiere al ahora famoso problema "FP vs. FNP": si FNP = FP, la verificación de la respuesta al acertijo es tan fácil como encontrarla. Sin embargo, si FNP ≠ FP, entonces existen "acertijos" para los cuales encontrar una solución es mucho más difícil que verificar la solución.

¡Creo que este problema es el problema abierto más antiguo de TCS, sin embargo, su formulación rigurosa se remonta a hace unos 30 años!

There seems to be a similar (yet somehow different!) proverb in the English language: "It's easy to be wise after the event" or "It's easy to be smart after the fact."

EDITAR: "¿Podemos factorizar números en poli-tiempo" es otro problema abierto de TCS, sin embargo, creo que es más joven que el problema mencionado anteriormente.

Aquí hay dos listas de problemas abiertos de TCS en la web:

También tenemos una lista aquí en CSTheory.

MS Dousti
fuente
1
Como lo estoy restringiendo a formulaciones rigurosas de problemas, supongo que la cuestión de factorizar y FP = FNP solo se puede formalizar una vez que tengamos máquinas de Turing y tiempo polinomial, etc.
Robin Kothari
@Robin: ¡No puede pedir problemas abiertos de TCS antiguos y formales, si ni siquiera hubiera computadoras en la vejez! :)
MS Dousti
1
@Sadeq: No me importa si la pregunta más antigua resulta ser una pregunta formulada en 1922. Insisto en preguntas rigurosamente formuladas porque de lo contrario la gente citará textos de 4000 años de antigüedad que afirman que alguna oración sobre el universo era una pregunta computacional disfrazada.
Robin Kothari
¿En qué año se formuló este problema?
Dave Clarke
3
@Sadeq: Cierto, pero esa no es la pregunta P versus NP a menos que alguien formalice el modelo, etc. Quiero decir que también podría representar alguna otra pregunta (digamos L versus NL, o P / poly versus NP / poly, o alguna pregunta en Un campo diferente). En segundo lugar, esa es una creencia común, no algo que se considere un problema abierto. No es algo que requiera pruebas, en su formulación original: es solo una observación sobre la vida.
Robin Kothari
3

Cuestiono su teoría de números excluyentes que involucra preguntas sobre si algunos conjuntos teóricos de números son finitos o infinitos como parte de TCS y definitivamente argumentaría lo contrario. los griegos cuestionaron si:

  • ¿hay algún número perfecto impar? [posiblemente considerado por euclides]

  • ¿hay un número infinito de primos gemelos?

TMxTMy

podría decirse que estos son dos problemas algorítmicos antiguos y los griegos fueron pioneros en los primeros TCS principalmente en forma de teoría de números y los primeros problemas de teoría de números son solo casos especiales de problemas de detención de Turings y evidencia circunstancial temprana de su dificultad. y existe una estrecha relación entre preguntar acerca de / encontrar / buscar pruebas y la teoría de la indecidibilidad.

Podría decirse que una nueva investigación muestra que la conjetura de Collatz, una vez considerada una curiosidad de la teoría de números, tiene profundos vínculos con la teoría de la computabilidad y puede estar justo en el límite entre los problemas indecidibles y decidibles. también el ejemplo que usted cita del décimo problema de hilbert muestra un vínculo muy fundamental entre la teoría de números y el TCS.

otras dos preguntas algorítmicas antiguas:

  • ¿Qué es un algoritmo eficiente o más eficiente para calcular el mcd divisor común más grande?

  • ¿Qué es un algoritmo eficiente o más eficiente para calcular primos?

acordó que la segunda pregunta está bastante relacionada con el factoring, pero no es lo mismo, por supuesto. fue considerado por el tamiz y euclides de eratóstenes. por supuesto, AKS demostró recientemente que estaba en P, pero incluso entonces el algoritmo no ha demostrado ser totalmente óptimo.

Existe una investigación TCS muy moderna sobre el algoritmo GCD de euclides (es decir, siglo XX) que demostró que los números de Fibonacci le dan el peor rendimiento. [No estoy seguro de quién primero mostró esto]

hasta que el algoritmo de euclides sea probado óptimo, podría decirse que el cálculo eficiente de gcd aún está abierto.

vzn
fuente
77
No estoy de acuerdo con la mayoría de lo que dice (el hecho de que pueda construir todo tipo de máquinas de Turing que se detengan si existen algunos objetos conjeturados no hace que estos problemas de existencia cuestionen la computabilidad). pero al final tiene un buen punto: generar determinísticamente un primo en algún rango es una versión moderna razonable de la antigua búsqueda para encontrar una "fórmula para primos". Me gustaría votar si escribes una respuesta centrada en este sentido
Sasho Nikolov,
1
Estoy de acuerdo con el comentario anterior: la conjetura de Poincare también puede formularse como un problema de detención para las máquinas de Turing, pero no se han realizado progresos utilizando técnicas específicamente de la comunidad de CS. Lo mismo puede decirse de tales problemas teóricos numéricos, computacionalmente relevantes como pueden ser.
cody
2

No estoy seguro de cuán seria es esta respuesta, pero ...

Realmente depende de cuán ampliamente esté dispuesto a definir su pregunta.

Seguramente "¿se puede construir una máquina inteligente?" es la pregunta abierta más antigua en CS que comenzó la informática, pero probablemente sea antigua en un milinio o dos que CS. ¿No? (Es una pregunta teórica, ya que pide una respuesta, no para la máquina en sí ...)

Una referencia natural a la búsqueda de una máquina inteligente sería el Golem ... http://en.wikipedia.org/wiki/Golem#History

Sariel Har-Peled
fuente
0

Puedo responder su pregunta con 100% de certeza por un período de tiempo. Si consideramos el período desde el documento seminal de Hartmanis y Stearns hasta cualquier punto en el futuro, el problema más antiguo en TCS que todavía está abierto es:

¿Cuál es la sobrecarga mínima necesaria para la simulación de TM deterministas?

T2(n)T(n)logT(n)

logT(n)

chazisop
fuente
1
Iniciar sesiónT(norte)
1
PAGSnortePAGS
1
Esto podría servir de aclaración, para beneficio de aquellos que no conocen esos documentos en detalle: ¿Qué tipo de TM se está simulando? ¿Qué tipo de máquina está haciendo la simulación?
funkstar
No creo que sea necesaria una aclaración. El hecho de que el modelo que se utiliza en el primer documento es el multitape TM es un hecho bien conocido, ya que contiene algunas de las definiciones centrales de TCS, además de que se menciona explícitamente en el título del documento de Hennie and Stearns.
chazisop
1
Su formulación de la pregunta abierta sigue siendo demasiado vaga, en mi opinión. Aunque es bien sabido en la comunidad de ToC que Hartmanis, Hennie y Stearns trabajan con TM multitape, eso simplemente hace que su respuesta sea inútil para aquellos en los muchos otros campos de TCS. Debería considerar al menos agregar el calificador "multitape" a la pregunta. (E incluso entonces, tiene el problema de que la simulación de Hartmanis y Stearns usa una TM de 1 cinta, mientras que la simulación de Hennie y Stearns usa una TM de 2 cintas.)
funkstar