Existencia de un algoritmo frente a su conocimiento

Question

En informática teórica, a menudo me he encontrado con una formulación "existe un algoritmo (polinómico), que calcula..." y en la prueba, el algoritmo estaba realmente descrito. Así que, de hecho, la prueba contiene algo más que la "existencia".

Mi pregunta es la siguiente: ¿hay algún problema para el que se sepa que existe un algoritmo con cierta complejidad computacional, pero la prueba no es constructiva y no se conoce (posiblemente) ningún algoritmo real?

Después de la edición @errorista y @Bressan: Gracias por la idea de la reducción de cualquier problema abierto en matemáticas a un algoritmo, cierto. Pero yo seguía buscando algún problema más "típico" de la informática, algún teorema del tipo "La multiplicación de matrices se puede hacer en ". $O(n^{2.1})$ pero no se conoce ningún algoritmo" o algo así. Tal vez puedas ayudarme a formalizar lo que quiero decir.

Answer 1

Considere la función $f\colon \mathbb{N} \to \{0, 1\}$ definido por $$f(x) = \begin{cases} 1 & \text{if $P$ holds} \\ 0 & \text{otherwise} \end{cases}$$ donde $P$ es un problema actualmente no resuelto, por ejemplo Conjetura de Goldbach .

Entonces, puedes demostrar que hay existe un algoritmo de tiempo constante que calcula $f$ En efecto, si $P$ tiene el algoritmo simplemente devuelve $1$ de lo contrario, simplemente devuelve $0$ .

Pero si conocía un algoritmo que calcule dicha función, también podríamos demostrar o refutar $P$ simplemente ejecutándolo en cualquier entrada.

Answer 2

Esto es similar en sabor a su pregunta, pero no se relaciona con la complejidad computacional.

Teorema de Rice establece, a grandes rasgos, que para cualquier propiedad no trivial de las funciones parciales $\mathbb{N} \to \mathbb{N}$ En general, es imposible determinar si una máquina de Turing dada induce o no una función parcial con esa propiedad.

Hay una prueba "casi constructiva" en el sentido de que si conocemos una máquina con la propiedad $P$ y una máquina sin $P$ entonces podemos construir un ejemplo explícito de una máquina cuyo $P$ -es incalculable. Sin embargo, el propio teorema de Rice nos dice que, en general, es imposible encontrar tal par de máquinas, aunque el par existe.

Answer 3

Considere el siguiente problema,

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

*Nota que aquí $0^n$ significa $n$ -concatenación doble, por ejemplo, $0^3 = 000$ .

En un post de informática, JeffE muestra que $f$ es computable, es decir, existe un algoritmo que resuelve este problema. Tenga en cuenta que no puede comprobar simplemente si $0^n$ se produce en $\pi$ atravesando dígitos de $\pi$ porque si no su algoritmo nunca se detendrá.

Sólo hay que considerar dos posibilidades.

• Para cada número entero positivo $n$ la cadena $0^n$ aparece en la representación decimal de $\pi$ . En este caso, el algoritmo que siempre devuelve 1 es siempre correcto.

• Hay un número entero mayor $N$ tal que $0^N$ aparece en la representación decimal de $\pi$ . En este caso, el siguiente algoritmo (con el valor $N$ codificado) es siempre correcto:

    Zeros-in-pi(n):
     if (n > N) then return 0 else return 1

Tenemos no idea de cuál de estas posibilidades es la correcta, o qué valor de $N$ es la correcta en el segundo caso. No obstante, se garantiza que uno de estos algoritmos es correcto. Así pues, existe un algoritmo para decidir si una cadena de $n$ los ceros aparecen en $\pi$ el problema es decidible.

Answer 4

Por fin he encontrado ese problema. Aquí, en este vídeo Donald Knuth habla de este problema. Resulta que realmente encontró el algoritmo. Pero por un día, sabía que tiene que haber un algoritmo eficiente, pero no sabía cuál era.

Steve Cook había demostrado un teorema muy sorprendente. Dijo que si... si se podía... si se tomaba un tipo de... un cierto tipo de ordenador que es muy limitado en su capacidad, y si se podía escribir un programa para ese tipo de ordenador tonto para resolver un problema, sin importar lo lento que fuera ese programa, entonces había una manera rápida de escribir un programa para un ordenador real. Así que, en otras palabras, si tomas un... un ordenador limitado en particular y si... si puede resolver un problema en absoluto, entonces hay una manera rápida de hacerlo en un ordenador real. Así que uno de los problemas que... que podíamos resolver con ese... con este... con este divertido ordenador era decidir si una cadena de letras era un palíndromo, si se leía o no lo mismo de atrás... de atrás a adelante... no, perdón, era una... era una concatenación de... de palíndromos... palíndromo seguido de otro palíndromo y así sucesivamente. Era sólo una curiosidad, quiero decir que nadie se preocupa realmente por la concatenación de palíndromos, pero ahí estaba, y... y así, de acuerdo con el teorema de Cook, ya que había una manera de que esta divertida máquina... reconociera estos... estos palíndromos, entonces debía haber una manera rápida de reconocer estas... estas concatenaciones de palíndromos en un ordenador normal. Pero no pude pensar en ninguna forma buena de hacerlo en un ordenador normal, me pareció que iba a ser un problema mucho más difícil. Así que, pensé que... Yo era un programador bastante bueno, pero aquí está este teorema diciendo que hay una manera de hacerlo y no puedo pensar en la forma de hacerlo. Esa es la primera vez que me quedé así de perplejo al decir que alguien tenía una buena manera y a mí no se me ocurría.