Soy nuevo en el campo de CS y he notado que en muchos de los artículos que leo, no hay resultados empíricos (sin código, solo lemas y pruebas). ¿Porqué es eso? Teniendo en cuenta que la informática es una ciencia, ¿no debería seguir el método
Sé que el problema de la detención es indecidible en general, pero hay algunas máquinas de Turing que obviamente se detienen y otras que obviamente no. De todas las máquinas de turing posibles, ¿cuál es la más pequeña donde nadie tiene una prueba de si se detiene o
En el prefacio de sus libros muy influyentes Automata, Languages and Machines (Volúmenes A, B), Samuel Eilenberg prometió tentadoramente que los Volúmenes C y D se ocupan de "una jerarquía (llamada la jerarquía racional) de los fenómenos no racionales ... utilizando relaciones racionales como una...
Estaba (y todavía estoy) realmente interesado en la respuesta a esta pregunta, porque esta es una variación interesante sobre la complejidad de los juegos que no se ha resuelto, así que ofrecí una recompensa. Pensé que la pregunta original era muy difícil, así que publiqué tres preguntas...
Dejar L = { n : el nt h dígito binario de π es 1 }L={n:the nth binary digit of π is 1}L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \} (donde se considera codificado en binario). Entonces, ¿qué podemos decir sobre la complejidad computacional de ? Está claro que . Y si no...
ST-conectividad es el problema de determinar si existe un camino dirigido entre dos vértices distinguidos y t en un gráfico dirigido G ( V , E ) . Si este problema se puede resolver en el espacio de registro, es un problema abierto de larga data. Esto se llama el N L vs L
Decidir si una fórmula booleana cuantificada como ∀ x1∃ x2∀ x3⋯ ∃ xnorteφ ( x1, x2, ... , xnorte) ,∀X1∃X2∀X3⋯∃Xnorteφ(X1,X2,...,Xnorte),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), siempre se evalúa como verdadero es un problema clásico completo de PSPACE....
Pensé en compartir esta pregunta, ya que podría ser interesante para otros usuarios aquí. Suponga que una función que está en una clase uniforme (como ) también está en una pequeña clase no uniforme (como A C 0 / p o l y , es decir, no uniforme A C 0 ), ¿esto implica que la función está contenida...
Estoy bastante confundido por la literatura de optimización continua y la literatura de TCS sobre qué tipos de programas matemáticos (continuos) (MP) se pueden resolver de manera eficiente y cuáles no. La comunidad de optimización continua parece afirmar que todos los programas convexos se pueden...
Quiero codificar una máquina simple de Turing en las reglas de un juego de cartas. Me gustaría convertirlo en una máquina universal de Turing para demostrar su integridad. Hasta ahora, he creado un estado de juego que codifica la máquina Turing de 2 estados y 3 símbolos de Alex Smith . Sin...
El número aproximado de coloraciones parece ser fácil en gráficos con exclusión menor utilizando el algoritmo de Jung / Shah. ¿Cuáles son otros ejemplos de problemas que son difíciles en gráficos generales pero fáciles en gráficos excluidos menores? Actualización 10/24 Parece seguir los...
He estado leyendo algunos artículos sobre tipos dependientes y contratos de programación. De la mayoría de lo que he leído, parece que los contratos se comprueban dinámicamente y los tipos dependientes se comprueban estáticamente. Ha habido algunos documentos que me han hecho pensar que es posible...
En esta publicación invitada de Josh Grochow en el complejo weblog, informa sobre un taller reciente dedicado a GCT que se celebró en Princeton en julio. Varios de los asistentes argumentaron que deberíamos usar GCT para atacar problemas más fáciles que vs. N P para construir la intuición y ver si...
Existen toneladas de problemas NP-completos y fuentes que los recopilan, por ejemplo, vea el libro de Garey y Johnson. Me interesaría ver una lista de problemas NEXP-complete también. ¿Hay uno disponible? Como supongo que no hay, abro esta pregunta (¿se supone que es una wiki comunitaria? No sé...
¿Hay un ejemplo interesante de un algoritmo aleatorio para un problema de búsqueda que siempre genera la misma respuesta (correcta), independientemente de su aleatoriedad interna, pero que explota la aleatoriedad para que su tiempo de ejecución esperado sea mejor que el tiempo de ejecución del más...
He estado leyendo " Semántica con aplicaciones " de Nielson & Nielson , y realmente me gusta el tema. Me gustaría tener un libro más sobre semántica del lenguaje de programación, pero realmente solo puedo obtener uno. Eché un vistazo al libro de Turbak / Gifford , pero es demasiado largo;...
Es bien sabido que una caminata aleatoria en la cuadrícula bidimensional volverá al origen con probabilidad 1. También se sabe que la misma caminata aleatoria en TRES dimensiones tiene una probabilidad estrictamente menor que 1 de regresar al origen . Mi pregunta es: ¿Hay algo en el medio? Por...
Dado un entero de longitud bits, ¿qué tan difícil es generar el número de factores primos (o alternativamente el número de factores) de ?NNNnnnNNN Si supiéramos la factorización principal de , entonces esto sería fácil. Sin embargo, si supiéramos el número de factores primos, o el número de...
La década de 1980 dio lugar a los modelos PRAM y BSP de cómputo paralelo. Parece que el apogeo de ambos modelos fue a finales de los 80 y principios de los 90. ¿Estas áreas aún están activas en términos de investigación para algoritmos paralelos? ¿Existen modelos más nuevos y sofisticados para la...
Me gustaría encontrar un algoritmo de tiempo polinómico que determine si el lapso de un conjunto dado de matrices contiene una matriz de permutación. Si alguien sabe si este problema es de una clase de complejidad diferente, sería igual de útil. EDITAR: He etiquetado esta pregunta con la...