Muchos expertos creen que la conjetura es cierta y la utilizan en sus resultados. Mi preocupación es que la complejidad depende en gran medida de la conjetura P ≠ N P.P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}P≠NPP≠NP\mathsf{P} \neq \mathsf{NP} Entonces mi pregunta es: Mientras no se pruebe la...
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...
Citando Wikipedia , "[El juego de la vida de Conway] tiene el poder de una máquina universal de Turing: es decir, cualquier cosa que se pueda calcular algorítmicamente se puede calcular dentro del Juego de la vida de Conway". ¿Se extienden dichos resultados a las versiones ruidosas de Conway's...
¿Alguien se atreve a intentar aclarar cuál es la relación de estos campos de estudio o tal vez incluso dar una respuesta más concreta a nivel de problemas? Como cuál incluye cuál asumiendo algunas formulaciones ampliamente aceptadas. Si entendí esto correctamente, cuando pasas de SAT a SMT...
Si observamos el teorema de la jerarquía DTIME, tenemos un registro debido a la sobrecarga en la simulación de una máquina de Turing determinista por una máquina universal: DTIME(flogf)⊊DTIME(f)DTIME(flogf)⊊DTIME(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) No tenemos este tipo de gastos...
Defina ioioio - SUBEXPSUBEXPSUBEXP como la clase de lenguajes LLL modo que haya un lenguaje L′∈∩ε>0TIME(2nε)L′∈∩ε>0TIME(2nε)L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}}) y para infinitamente nnn , LLL y L′L′L' estén de acuerdo en todos los casos de longitud nnn . (Es decir, esta es...
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...
¿El lenguaje { } está libre de contexto o no?unayosijdok El | i≠j,i≠k,j≠k unayosijdok El | yo≠j,yo≠k,j≠ka^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k Me di cuenta de que he encontrado casi todas las variantes de esta pregunta con diferentes condiciones sobre la relación entre i, j y k, pero no...
No parece que se sepa esto, pero ¿hay algún límite inferior interesante sobre la complejidad de la multiplicación de matrices en el modelo de computación cuántica? ¿Tenemos alguna intuición de que podemos vencer la complejidad del algoritmo Coppersmith-Winograd usando computadoras...
No determinismo Bounded asocia una función con una clase de las lenguas aceptadas por las máquinas de Turing deterministas-delimitada de recursos, para formar una nueva clase - . Esta clase consta de aquellos lenguajes que son aceptados por alguna máquina de Turing no determinista obedece a los...
Enseño un curso de algoritmos avanzados y me gustaría incluir algunos temas relacionados con el aprendizaje automático que serán de interés para mis alumnos. Como resultado, me gustaría escuchar las opiniones de las personas sobre los resultados algorítmicos más interesantes / mejores actualmente...
Richard J. Lipton ha sido seleccionado como el ganador del Premio Knuth 2014 "por Introducción de nuevas ideas y técnicas". ¿Cuáles son para usted las principales ideas y técnicas nuevas que desarrolló Lipton? Nota. Esta pregunta se convertirá en wiki de la comunidad, por favor ponga una idea,...
Es bien sabido que una expresión regular puede ser reconocida por un autómata finito no determinista de tamaño proporcional a la expresión regular, o por un FA determinista que es potencialmente exponencialmente más grande. Además, dada una cadena una expresión regular , la NFA puede probar la...
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...
En un par de preguntas recientes ( q1 q2 ), se ha debatido sobre "Teoría A" versus "Teoría B", aparentemente para capturar la división entre el estudio de los lenguajes de lógica y programación y el estudio de algoritmos y complejidad. Esta terminología era nueva para mí, y una búsqueda rápida en...
¿Cuáles serían las desagradables consecuencias de NP = PSPACE? Me sorprende no haber encontrado nada sobre esto, dado que estas clases se encuentran entre las más famosas. En particular, ¿tendría alguna consecuencia en las clases
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...
¿Hay algún lenguaje de programación (funcional) donde todas las funciones tengan una forma canónica? Es decir, cualquiera de las dos funciones que devuelven los mismos valores para todo el conjunto de entrada se representa de la misma manera, por ejemplo, si f (x) devolvió x + 1 yg (x) devolvió x +...
Se sabe que con un conjunto contable de algoritmos (caracterizado por un número de Gödel), no podemos calcular (construir un algoritmo binario que verifique la pertenencia) todos los subconjuntos de N. Una prueba podría resumirse como: si pudiéramos, entonces el conjunto de todos los subconjuntos...
En una oración: ¿la existencia de una jerarquía para implicaría algún resultado de aleatorización?B P T I M EBPTIME\mathsf{BPTIME} Una pregunta relacionada pero más vaga es: ¿la existencia de una jerarquía para implica algún inferior difícil? ¿La resolución de este problema choca contra una...