Suponga que P = NP es verdadero. ¿Habría alguna aplicación práctica para construir una computadora cuántica, como resolver ciertos problemas más rápido, o cualquier mejora sería irrelevante debido al hecho de que P = NP es cierto? ¿Cómo caracterizaría la mejora en la eficiencia que se produciría si...
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...
Soy un principiante trabajando en métodos que prueban la equivalencia del programa. He leído algunos artículos sobre la definición de relaciones lógicas o simulaciones para demostrar que dos programas son equivalentes. Pero estoy bastante confundido acerca de estas dos técnicas. Solo sé que las...
La mayoría de los asistentes de prueba (¿todos?) Tienen errores de solidez corregidos ocasionalmente. Sin embargo, de los que he visto, estos errores suelen ser difíciles de encontrar involuntariamente, y los resultados probados antes de que el error se solucione generalmente se mantienen después...
Recientemente se hicieron dos preguntas en cs.se que estaban relacionadas o tenían un caso especial equivalente a la siguiente pregunta: Suponga que tiene una secuencia de números tales que Descomponerlo en la suma de dos permutaciones, y , de , de modo que . n ∑ n i = 1 a i = n ( n + 1 ) . π σ 1...
El reciente resultado innovador del límite inferior de la complejidad del circuito de Ryan Williams proporciona una técnica de prueba que utiliza el resultado del límite superior para demostrar la complejidad de los límites inferiores. Suresh Venkat en su respuesta a esta pregunta, ¿hay resultados...
El siguiente problema surgió durante la investigación, y es sorprendentemente limpio: Tienes una fuente de monedas. Cada moneda tiene un sesgo, es decir, una probabilidad de que caiga en "cabeza". Para cada moneda, independientemente, hay una probabilidad de 2/3 de que tenga un sesgo de al menos...
Los algoritmos clásicos pueden resolver 3-SAT en tiempo (aleatorizado) o 1.3303 n tiempo (determinista). (Referencia: Mejores límites superiores en SAT )1.3071norte1.3071norte1.3071^n1.3303norte1.3303norte1.3303^n A modo de comparación, el uso del algoritmo de Grover en una computadora cuántica...
Es bien sabido por el teorema de Ladner que si , entonces existen infinitos problemas -intermediate ( ). También hay candidatos naturales para este estado, como Graph Isomorphism y varios otros, consulte Problemas entre P y NPC . Sin embargo, se sabe que la gran mayoría de la multitud de...
Esta es una pregunta de seguimiento para ¿Cuál es la diferencia entre pruebas y programas (o entre proposiciones y tipos)? ¿Qué programa correspondería a una prueba no constructiva (clásica) de la forma ? (Suponga que es una relación decidible interesante, por ejemplo, -th TM no se detiene en...
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...
He escuchado que existen argumentos heurísticos en física estadística que arrojan resultados en la teoría de probabilidad para la cual se desconocen o son muy difíciles las pruebas rigurosas. ¿Cuál es un ejemplo de juguete simple de tal fenómeno? Sería bueno si la respuesta asumiera pocos...
Sea fff una función booleana y pensemos en f como una función desde {−1,1}n{−1,1}n\{-1,1\}^n hasta . En este lenguaje, la expansión de Fourier de f es simplemente la expansión de f en términos de monomios libres cuadrados. (Estos monomios forman una base para el espacio de funciones reales en . La...
Se conjetura que ya que lo contrario implicaría \ mathsf {PH} = \ Sigma_2 . El teorema de Ladner establece que si \ mathsf {P} \ ne \ mathsf {NP} entonces \ mathsf {NPI}: = \ mathsf {NP} \ setminus (\ mathsf {NPC} \ cup \ mathsf {P}) \ ne \ emptyset . Sin embargo, la prueba no parece generalizarse...
¿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 +...
Recientemente, un amigo mío (trabajando en TCS) mencionó en una conversación que "quería ver / saber todo (o la mayor cantidad posible) de los hermosos resultados en TCS en su vida". Esto me hizo preguntarme sobre los hermosos resultados en esta área y, por lo tanto, la motivación para la siguiente...
Una cadena tiene 2n2n2^n subsecuencias, pero generalmente no son todas distintas. ¿Cuál es la complejidad de encontrar la frecuencia máxima de cualquier subsecuencia? Por ejemplo, la cadena "subsecuencia" contiene 7 copias de la subsecuencia "demandar" y este es el máximo. Ejemplo de código de...
Deje que denote un problema (decisión) en NP y deje que # X denote su versión de conteo.XXXXXX ¿En qué condiciones se sabe que "X es NP-completo" ⟹⟹\implies ¿"#X es # P-completo"? Por supuesto, la existencia de una reducción parsimoniosa es una de esas condiciones, pero esto es obvio y la única...
Los métodos polinómicos , por ejemplo, el teorema combinatorio de Nullstellensatz y Chevalley-Warning son herramientas poderosas en la combinatoria aditiva. Al representar un problema con los polinomios adecuados, pueden garantizar la existencia de una solución o el número de soluciones para los...
La publicación de blog de Scott Aaronson hoy dio una lista de interesantes problemas / tareas abiertas en complejidad. Uno en particular me llamó la atención: Cree una biblioteca pública de instancias 3SAT, con la menor cantidad de variables y cláusulas posibles, que tendrían consecuencias...