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

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.

¿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.

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".

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):

$(\frac{q}{N})=1$$(\frac{q}{N})$

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?

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:

• http://www.c2.com/cgi/wiki?OpenProblemsInComputerScience
• http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science

También tenemos una lista aquí en CSTheory.

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?

$TM_x$$TM_y$

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.

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

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?

$T^{2}(n)$$T(n)$$\log T(n)$

$\log T(n)$