Una matriz se llama totalmente regular si todas sus submatrices cuadradas tienen rango completo. Tales matrices se usaron para construir superconcentradores. ¿Cuál es la complejidad de decidir si una matriz dada es totalmente regular sobre los racionales? Sobre campos finitos? Más en general,...
La paridad y son como gemelos inseparables. O eso parece durante los últimos 30 años. A la luz del resultado de Ryan, habrá un renovado interés en las clases pequeñas.A C0 0AC0AC^0 Furst Saxe Sipser a Yao a Hastad son todas paridades y restricciones aleatorias. Razborov / Smolensky es un polinomio...
Actualmente, el cálculo de los reales en los idiomas más populares todavía se realiza a través de operaciones de coma flotante. Por otro lado, teorías como la efectividad de tipo dos (TTE) y la teoría de dominios han prometido durante mucho tiempo el cálculo exacto de los reales. Claramente, el...
Feedback Vertex Set es NP-complete para gráficos generales. Se sabe que es NP-completo para gráficos limitados de grado 8 debido a una reducción de la cubierta del vértice. El artículo de Wikipedia dice que es polisoluble para gráficos limitados de grado 3 y NP-completo para gráficos limitados de...
EDITAR el 2011/02/08: Después de encontrar y leer algunas referencias, decidí separar la pregunta original en dos. Aquí está la parte relativa a UP vs NP, para la parte de clases sintácticas y semánticas, consulte Beneficios para clases sintácticas y semánticas . (el tiempo polinómico...
Actualmente estoy interesado en obtener (o construir) y estudiar fórmulas 3-CNF que son insatisfactorias y de tamaño mínimo. Es decir, deben consistir en la menor cantidad posible de cláusulas (m = 8 preferiblemente) y la menor cantidad posible de variables distintas (n = 4 o más), de modo que...
Mi teorema favorito en teoría de la complejidad es el teorema de la jerarquía del tiempo. Sin embargo, esto se hizo en 1965. Quería saber si había algo similar para Quantum Computing. Además, si no, ¿cuáles son las personas / grupos que trabajan en esta
Deje ser una función de valor entero tal que esté en . ¿Se sigue que2 F # P F # PFFF2 F2F2F# P#P\#PFFF está en ? ¿Hay razones para creer que es poco probable que esto se cumpla siempre? ¿Alguna referencia que deba saber?# P#P\#P Sorprendentemente, esta situación surgió (con una constante mucho...
Supongamos que es el peor tiempo de ejecución de un problema en una entrada de tamaño . Hagamos el problema un poco extraño arreglando para pero para .f(n)f(n)f(n)nnnf(n)=n2f(n)=n2f(n) = n^2n=2kn=2kn=2kf(n)=nf(n)=nf(n) = nn=2k+1n=2k+1n=2k+1 Entonces, ¿cuál es el límite inferior del problema? La...
Parity-P es el conjunto de lenguajes reconocidos por una máquina de Turing no determinista que solo puede distinguir entre un número par o un número impar de rutas de "aceptación" (en lugar de un número cero o no cero de rutas de aceptación). Por lo tanto Paridad-P es básicamente PP atrofiado...
Defina la complejidad gaussiana de una matriz como el número mínimo de operaciones elementales de fila y columna requeridas para llevar la matriz a la forma triangular superior. Esta es una cantidad entre 0 y n 2 (a través de Gaussian elemination). La noción tiene sentido sobre cualquier...
El problema de detención para las máquinas de Turing es quizás el conjunto canónico indecidible. Sin embargo, demostramos que hay un algoritmo que decide casi todas las instancias del mismo. Por lo tanto, el problema de detención se encuentra entre la creciente colección de quienes exhiben el...
Mafia es un popular juego de rol en fiestas, una descripción detallada está disponible en wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 . Básicamente, funciona de la siguiente manera: Al principio, a cada uno de los jugadores se le asigna un rol en secreto, ya sea alineado con la mafia...
¿Todas las funciones cuyo peso de Fourier se concentra en los conjuntos de tamaño pequeño (o términos con bajo grado) se calculan mediante circuitos
La famosa conjetura del isomorfismo de Berman y Hartmanis dice que todos los lenguajes completos son polinomiales en tiempo isomorfo (p-isomorfo) entre sí. El significado clave de la conjetura es que implica . Fue publicado en 1977, y una evidencia de apoyo fue que todos los completos de conocidos...
¿Qué se sabe sobre la complejidad exacta del problema de supercuerdas más corto? ¿Se puede resolver más rápido que O∗(2n)O∗(2n)O^*(2^n) ? ¿Existen algoritmos conocidos que resuelvan la supercadena más corta sin reducir a TSP? UPD: suprime los factores polinomiales.O∗(⋅)O∗(⋅)O^*(\cdot) El...
Creo que sería una buena idea hacer una lista de teoremas que indiquen que P no es igual a NP si y solo si tales y tales salidas, alguna clase de complejidad está contenida en otra clase de complejidad y así sucesivamente.
Sea una fórmula CNF satisfactoria con n variables y m cláusulas. Sea S F 1 el espacio de solución de F 1 .F1F1F_1nortennmetrommSF1SF1S_{F_1}F1F1F_1 Considere el problema de determinar, dado , otra Fórmula CNF F 2 con el mismo conjunto de variables que F 1 , con S F 2 = S F 1 (el mismo espacio de...
IP = PSPACE aparece como el ejemplo canónico de un resultado no relativizante, y la prueba de esto es que existe un oráculo tal que , mientras que {\ sf CONP} ^ O \ subseteq {\ sf PSPACE} ^ O para todos los oráculos O .c o N P O ⊈ I P O c o N P O ⊆ P S P A C E O OOOOc o N PO⊈ I...
¿Estoy en lo cierto al entender que probar un problema NP completo es un éxito de investigación? Si es así, ¿por