Esta pregunta se migró de Computer Science Stack Exchange porque se puede responder en Teorematic Computer Science Stack Exchange. Migrado hace 3 años . En el artículo de Ciencia de 2016 " Realización de un algoritmo Shor escalable " [ 1 ], los autores factorizan 15 con...
Veamos el futuro dentro de 30 años. Seamos optimistas y asumamos que las áreas relacionadas con el aprendizaje automático continúan desarrollándose tan rápido como lo que hemos visto en los últimos 10 años. Eso sería genial, pero ¿cuál sería el papel de los algoritmos tradicionales en un futuro...
Fijo un lenguaje regular LLL en un alfabeto ΣΣ\Sigma , y considero que el siguiente problema al que llamo programación carta de LLL . Informalmente, la entrada me da nnn letras y un intervalo para cada letra (es decir, una posición mínima y máxima), y mi objetivo es colocar cada letra en su...
Ha pasado más de un año desde su retracción y corrección de enero de 2017. ¿Hay novedades? Si no, ¿es normal que la validación demore tanto? Esperaría que recibiera mucha atención. ¿Alguien notable ha hablado para apoyar / dudar del resultado cuasi
La prueba reciente e increíblemente hábil de la conjetura de la sensibilidad se basa en la construcción explícita * de una matriz , definida recursivamente de la siguiente manera: y, para , En particular, es fácil ver que para todo .An∈{−1,0,1}2n×2nAn∈{−1,0,1}2n×2nA_n\in\{-1,0,1\}^{2^n\times...
La redacción exacta del título se debe a Anand Kulkarni (quien propuso que se creara este sitio). Esta pregunta se hizo como una pregunta de ejemplo, pero tengo una curiosidad increíble. Sé muy poco acerca de la geometría algebraica y, de hecho, solo tengo una comprensión superficial y de pregrado...
x∈Rnx∈Rnx \in \mathbb{R}^n∥x∥0<k‖x‖0<k\|x\|_0 < kAxAxAxAAARRRnnnR≪nR≪nR \ll nAAAkkk-parte xxx con RRR tan pequeño como O(kno(1))O(kno(1))O(k n^{o(1)}) . Puede que no tenga los parámetros más conocidos, pero esta es la idea general. Mi pregunta es: ¿hay fenómenos similares en otros entornos?...
Scott Aaronson propuso un desafío interesante : ¿podemos usar supercomputadoras hoy para ayudar a resolver problemas de CS de la misma manera que los físicos usan colisionadores de partículas grandes? Más concretamente, mi propuesta es dedicar parte de la potencia informática mundial a un...
Esto está en la línea de " Algoritmos del libro ". Aunque las reducciones también son algoritmos, pensé que era dudoso pensar en una reducción en respuesta a la pregunta sobre los algoritmos del libro. Por lo tanto, una consulta por separado! Las reducciones de todo tipo son bienvenidas....
El teorema original de la jerarquía del tiempo no determinista se debe a Cook (el enlace es a S. Cook, una jerarquía para la complejidad del tiempo no determinista , JCSS 7 343–353, 1973). El teorema establece que para cualquier número real y , si entonces NTIME ( ) está estrictamente contenido en...
Aquí hay algunas formas de analizar el tiempo de ejecución de un algoritmo: 1) Análisis del peor de los casos: tiempo de ejecución en la peor instancia. 2) Análisis de casos promedio: tiempo de ejecución esperado en una instancia aleatoria. 3) Análisis amortizado: tiempo promedio de ejecución en...
¿Cuáles son las referencias básicas? ¿Hay alguna buena encuesta de alto nivel de SGT y sus aplicaciones a CS en general y al aprendizaje automático más
En 1999, Petra Schuurman y Gerhard J. Woeginger publicaron el documento "Algoritmos de aproximación del tiempo polinómico para la programación de máquinas: diez problemas abiertos" . Desde entonces, que yo sepa, no han aparecido revisiones que conciernen a la misma lista de problemas. Por lo tanto,...
No entiendo por qué casi todos los solucionadores de SAT usan CNF en lugar de DNF. Me parece que resolver SAT es más fácil usando DNF. Después de todo, solo tiene que explorar el conjunto de implicantes y verificar si uno de ellos no contiene tanto una variable como su negación. Para CNF, no existe...
¿Qué se sabe sobre la complejidad temporal del siguiente problema, que llamamos 3-MUL? Dado un conjunto de n enteros, ¿hay elementos a, b, c \ en S tales que ab = c ?n a , b , c ∈ S a b = cSSSnnna,b,c∈Sa,b,c∈Sa,b,c\in Sab=cab=cab=c Este problema es similar al problema 3-SUM, que pregunta si hay...
Peter Shor planteó un punto interesante en relación con un intento de responder una pregunta anterior sobre la complejidad de resolver el cubo n×n×nn×n×nn \times n \times n Rubik. Había publicado un intento bastante ingenuo de mostrar que debe estar contenido en NP. Como Peter señaló, mi enfoque...
Esta pregunta es sobre la relación entre la multiplicación normal de números binarios y la multiplicación polinómica mod 2. Para concretar la pregunta, idealmente quisiera saber si hay una mejor solución para la pregunta de Knuth vol. 2, 3ª edición, página 420 que la que figura en el libro. "¿Se...
Los últimos meses comencé a darme conferencias sobre la elección social, el teorema de la flecha y los resultados relacionados. Después de leer sobre los resultados seminales, me pregunté qué sucede con las preferencias de orden parcial, la respuesta está en el documento de Pini et al. : Agregando...
Me acabo de dar cuenta de que he estado asumiendo que la respuesta a mi pregunta es "sí", pero no tengo una buena razón. Me imagino que tal vez haya un recolector de basura que probablemente solo presente peor desaceleración. ¿Hay alguna referencia definitiva que pueda citar? En mi caso, estoy...
Esta pregunta es un seguimiento de la pregunta sobre los algoritmos de ADN formulada por Aadita Mehra . En los comentarios allí, Joe Fitzsimmons dijo, en parte: [E] l radio del sistema debe escalar proporcionalmente a la masa para evitar esto. El poder computacional se escala a lo sumo...