¿Hay problemas decidibles para los cuales, sin algoritmo, podemos dar límites de tiempo?

12

¿Hay problemas decidibles de tal manera que para ningún algoritmo que resuelva el problema podamos dar un límite de tiempo en función de la longitud n de la instancia de entrada?

Llegué a esta pregunta porque estaba pensando en lo siguiente:

Supongamos que tenemos un problema recursivamente enumerable pero indecidible. Supongamos además que soy un "sí", una instancia del problema. Entonces, para ningún algoritmo que identifique las instancias "sí" del problema, podemos dar un límite de tiempo en términos del tamaño n de I. Porque si pudiéramos dar dicho límite de tiempo, podríamos decidir el problema, ya que podríamos simplemente concluya que soy una instancia de "no" cuando se excede el límite de tiempo.

Como no podemos dar un límite de tiempo para problemas recursivamente enumerables e indecidibles (para el tiempo de cálculo para instancias de "sí"), me preguntaba si también hay problemas decidibles para los que no podemos dar un límite de tiempo.

Hermann
fuente
99
Hay un tiempo trivial limitado en tales algoritmos: ejecute el algoritmo y devuelva el número de pasos realizados por ese algoritmo. Por otro lado, es fácil construir ejemplos para los cuales es difícil establecer límites que sean fáciles de entender o expresar, por ejemplo, la función ackermann.
cody
2
Tendrás que ser más preciso. Si habla de funciones (matemáticas), entonces sí, hay una función que coincide con el tiempo de ejecución de cualquier máquina de Turing (de hecho, hay más funciones que las máquinas de Turing). Si habla de funciones computables o, de manera equivalente, algoritmos, @cody le da la respuesta: simplemente ejecute la máquina Turing para decidir el problema y cuente su tiempo de ejecución.
Alex ten Brink
8
nn
8
¿Puedo sugerir una revisión? Para evitar la respuesta trivial, supongamos que definimos la frase "podemos dar un límite de tiempo" que significa "podemos calcular un límite superior en el peor tiempo de ejecución más rápido que ejecutando el algoritmo en todas las instancias de tamaño n". O tal vez "todas las instancias" deberían ser "una sola instancia".
Jeffε
1
Su argumento depende de que su función con límite de tiempo sea computable total . Es bien sabido que esto no se puede hacer, pero si esa es su pregunta (es decir, hay funciones computables parciales sin extensión de función computable total), entonces la pregunta no es de nivel de investigación. Consulte las preguntas frecuentes para obtener sugerencias sobre dónde podría hacer este tipo de preguntas.
Kaveh

Respuestas:

13

AIn

f(n)=maxiIn(n)  time(A(i)),
In(n)ntime(A(i))Ai

Si usamos términos algebraicos simples (sin recurrencia de ningún tipo) como definición de conciso, entonces creo que la respuesta es no: hay problemas que pueden decidirse pero cuya complejidad no es elemental. Es decir, no existe una pila de la forma que limita el tiempo de ejecución de un algoritmo para un problema de tamaño n.2222n

Espero haber entendido su pregunta de la manera correcta.

Markus
fuente
6

Esta es una versión ligeramente diferente de su pregunta que la de Marcus, pero a la luz de su explicación de cómo llegó a pensar en esta pregunta, puede estar más cerca de lo que está buscando.

A veces se puede demostrar que un problema es decidible, sin poder exhibir el algoritmo para ello. El ejemplo más famoso de este tipo de cosas es el trabajo de Robertson y Seymour en gráficos menores, que muestra que cualquier propiedad gráfica hereditaria se puede decidir en tiempo polinómico, al verificar la presencia de una lista finita adecuada de menores prohibidos. Su prueba muestra solo que existe una lista finita de menores prohibidos, pero no proporciona una receta para encontrar la lista.

No soy un experto en el área, así que no conozco de antemano un ejemplo específico de una propiedad gráfica hereditaria para la cual no podemos exhibir un algoritmo porque no conocemos la lista de menores prohibidos y no conocemos otra forma de resolver el problema, pero sospecho que existen tales ejemplos. (¡Y podemos limitar el tiempo de ejecución para encontrar un ejemplo si existe, ya que sabemos que hay como máximo 8 mil millones de personas en el mundo y, en el peor de los casos, podríamos preguntarles a todos!)

Una observación más: Como sabemos que la comprobación de un menor de edad puede hacerse en tiempo, se podría argumentar que en todos los casos proporcionados por el algoritmo de Robertson-Seymour, que tenemos un "salto" de en el tiempo de ejecución. Sin embargo, diría que esto es una especie de trampa, si no tenemos límites en la constante.O(n3)O(n3)

Timothy Chow
fuente
2
Pero si elige un conjunto explícito de menores excluidos, puede exhibir un algoritmo. Mejor sería elegir alguna propiedad hereditaria que no haya sido estudiada. Sin embargo, esto es un poco más complicado de hacer.
Timothy Chow
2
Es bastante tangencial a su punto, pero: las propiedades de gráficos cerrados menores pueden de hecho decidirse en el tiempo research.nii.ac.jp/~k_keniti/quaddp1.pdf . O(n2)
Emil Jeřábek
1
@ EmilJeřábek: aún más tangencialmente, decidir si un gráfico de una familia cerrada menor satisface una propiedad de primer orden se puede hacer en tiempo lineal: arxiv.org/abs/1109.5036
András Salamon
1
Por cierto, Kowarabayashi y Wollan reclaman un límite en la constante en su documento STOC 2011 dsi.uniroma1.it/~wollan/PUBS/shorter_struct_web.pdf que también informa sobre el progreso adicional que "aún no está completamente escrito". Sin embargo, no puedo extraer fácilmente un enlace explícito de este documento.
András Salamon
2
Para tal ejemplo, tiene gráficos con una cubierta plana. Extrañamente, casi conocemos una lista: hay 31 menores prohibidos y un 32o potencial, pero para este último está abierto si tiene una cubierta plana o no. Por lo tanto, no tenemos un algoritmo para esta clase de gráficos. Ver por ejemplo: fi.muni.cz/~hlineny/papers/plcover20-gc.pdf
Denis
3

Solo para agregar una perspectiva diferente, permítanme recordar que no todos los problemas tienen una complejidad "intrínseca", que es probablemente la consecuencia más interesante y descuidada del teorema de aceleración de Blum.

Esencialmente, el teorema establece que, fijando una aceleración deseada g, siempre puede encontrar un problema computacional P tal que para cualquier programa que resuelva P exista otro programa que todavía resuelva P y ejecute g veces más rápido que el anterior.

Por lo tanto, para este tipo de problemas no puede dar un límite de tiempo. Sorprendente y bastante sorprendente resultado. Por supuesto, P tiene una gran complejidad.

Andrea Asperti
fuente
¿Por qué P tiene una complejidad muy grande?
Debido a que el proceso de aceleración puede iterarse, por lo tanto, debe ser compatible con una cadena infinita de algoritmos de complejidad decreciente.
Andrea Asperti
3

Markus se ocupa del aspecto teórico de su pregunta. Más prácticamente, una forma interesante de entender su pregunta es: ¿hay problemas decidibles para los que no conocemos ningún límite de tiempo?

La respuesta es sí: por ejemplo, puede suceder que tenga un semi-algoritmo para las instancias SÍ de su problema, y ​​un semi-algoritmo para las instancias NO. Esto le permite decidir su problema, pero no tiene límite de tiempo.

Aquí hay un ejemplo genérico: suponga que tiene un sistema axiomático que le permite probar todas las identidades verdaderas en algunos álgebra. Además, sabe que las identidades falsas siempre son presenciadas por una estructura finita.

Luego tiene el siguiente algoritmo para decidir si una identidad es verdadera: enumere en pruebas paralelas y estructuras finitas, y deténgase cuando encuentre una prueba de o una estructura que atestigüe que falso. Se le da un algoritmo correcto, pero sin límite de complejidad, a menos que se puede acotar el tamaño de pruebas y estructuras finitas con respecto al .IIII

Un ejemplo de esto es la lógica lineal afín (LLW): ahora se sabe que es completa en torre [1], pero durante algún tiempo no se conocieron límites, y solo se mostró la capacidad de decisión, utilizando entre otras técnicas la propiedad de modelo finito [2] .

Referencias

[1] Complejidades no elementales para ramificar VASS, MELL y extensiones. Ranko Lazic y Sylvain Schmitz. CSL-LICS 2014

[2] La propiedad del modelo finito para varios fragmentos de lógica lineal. Yves Lafont, J. Symb. Lógica. 1997

Denis
fuente
-4

Como otros han dicho, la pregunta no se formula de una manera que evite una respuesta trivial, sin embargo, hay algunos conceptos en TCS y teoría de números que están relacionados / similares.

1) en los teoremas de la jerarquía del espacio y el tiempo se requiere el concepto de funciones "construibles en el tiempo" y "construibles en el espacio" . Las funciones no construibles en el tiempo y no en el espacio existen y conducen a propiedades inusuales que se encuentran en los teoremas de Blum, tales como los teoremas "gap, speedup". La mayoría de las clases de complejidad estándar (¿todas?) se definen en términos de funciones construibles de espacio y tiempo.

2) la función ackerman es recursiva total pero no recursiva primitiva y esto tiene implicaciones para su límite de tiempo. Las funciones recursivas primitivas en cierto sentido representan las operaciones matemáticas "básicas".

3) hay thms sobre secuencias de teoría de números que no se pueden calcular en aritmética de peano que se pueden interpretar como la creación de límites de tiempo no computables en un sentido, como la secuencia de Goodstein o los thms de Paris Harrington

vzn
fuente
55
No es una respuesta a la pregunta.
Kaveh