Después de la discusión sobre los límites inferiores para 3SAT [ 1 ], me pregunto cuáles son los principales resultados del límite inferior formulados como compensaciones espacio-tiempo. Estoy excluyendo resultados como, por ejemplo, el teorema de Savitch; una buena entrada se centraría en un solo...
En un artículo titulado "Sobre la negabilidad en la cadena de referencia común y el modelo aleatorio de Oracle", Rafael Pass escribe: Observamos que al probar la seguridad de acuerdo con la definición estándar de conocimiento cero en el modelo RO [Random Oracle], el simulador tiene dos ventajas...
Supongamos que tenemos un conjunto S de gráficos (gráficos finitos, pero un número infinito de ellos) y un grupo P de permutaciones que actúa sobre S. Instancia: una permutación p en P. Pregunta: ¿Existe un gráfico g en S que admite el automorfismo p? ¿Es este problema NP completo para...
Una fórmula Monotone-2CNF es una fórmula CNF donde cada cláusula está compuesta por exactamente 2 literales positivos. Ahora, tengo una fórmula Monótono-2CNF . Sea S el conjunto de las tareas satisfactorias de F. También tengo un oráculo O que puede dar la siguiente información:FFFSSSFFFOOO La...
En una aplicación que estoy considerando, necesito saber la complejidad de comunicación del siguiente problema: Dado , sea S el conjunto de enteros de 1 a n . Alice, Bob y Carol reciben cada uno un subconjunto de S , denotado por A , B y C , respectivamente. Ellos quieren comprobar si A , B y C...
La clase de complejidad PPAD generalmente se define al indicar que Fin de línea está completa con PPAD. El fin de la línea es un problema de búsqueda. La entrada consiste en un gráfico dirigido en el que cada nodo tiene un grado de entrada y salida como máximo 1. El gráfico viene dado por una...
La pregunta se me ocurrió cuando recibí la respuesta de Dana Moshkovitz a otro tema . Sea LLL un lenguaje NP , y sea RLRLR_L la relación NP respectiva . Sabemos que existe algún polinomio pagpagp tal que: ∀ x ∈ L ,, ∃ w ∈0 , 1p ( | x | )( x , w ) ∈ RL∀X∈L,,∃w∈0 0,1pag(El |XEl |)(X,w)∈RL\forall x...
Se sabe que determinar si una variedad múltiple triangulada de 3 es una esfera 3 está en NP, a través del trabajo de Saul Schleimer en 2004: "El reconocimiento de la esfera se encuentra en NP" arXiv: math / 0407047v1 [math.GT] . Me pregunto si esto se ha establecido para NP-completo en los últimos...
Digamos que tenemos una red neuronal de alimentación de una sola capa con k entradas y una salida. Calcula una función a partir de , es bastante fácil ver que tiene al menos la misma potencia de cálculo que A C 0 . Solo por diversión, llamaremos al conjunto de funciones computables por una red...
Deje que un polinomio multivariable con coeficientes más de un campo F . El multilinearization de p , denotada por p , es el resultado de sustituir repetidamente cada x d i con d > 1 por x i . El resultado es obviamente un polinomio
Muchas clases de complejidad definidas con máquinas de Turing tienen definiciones en términos de circuitos uniformes. Por ejemplo, P también se puede definir usando circuitos de tamaño polinómico uniforme, y de manera similar BPP, NP, BQP, etc. se pueden definir con circuitos uniformes....
El problema del ciclo hamiltoniano (HC) consiste en encontrar un ciclo que atraviese todos los vértices en un gráfico no dirigido dado. El problema del vendedor ambulante (TSP) consiste en encontrar un ciclo que atraviese todos los vértices en un gráfico ponderado de borde dado y minimice la...
DLogTimeDLogTime\mathsf{DLogTime} yNLogTimeNLogTime\mathsf{NLogTime} son dos de las clases de complejidad más pequeñas que tenemos. (Tenga en cuenta que la jerarquía de tiempo logarítmicoLHLH\mathsf{LH} es igual aAC0AC0\mathsf{AC}^0 y estos son los dos primeros niveles deLHLH\mathsf{LH} ). Después...
Aquí está el problema: Tenemos un cuadrado con algunos números de 1..N en algunas celdas. Es necesario para determinar si se puede completar en un cuadrado mágico. Ejemplos: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _ ¿Es este problema...
Una observación asociada con la criptografía asimétrica es que algunas funciones son (se cree que son) fáciles de realizar en una dirección pero difíciles de invertir. Además, si existe alguna información de 'trampa' que permite que la operación inversa se calcule rápidamente, entonces el problema...
La cubierta de vértices se puede reducir fácilmente a conjunto independiente y viceversa. Sin embargo, en el contexto de la complejidad parametrizada, el conjunto independiente es más difícil que Vertex Cover. Existe un kernel con vértices para Vertex Cover, pero Independent Set es W 1...
Es bien sabido que existe un algoritmo óptimo para el peor de los casos para calcular el código Huffman en el tiempo . Esto se mejora de dos maneras ortogonales:θ(nlgn)θ(nlgn)\theta(n\lg n) Los códigos libres de prefijos óptimos se pueden calcular más rápido si el conjunto de frecuencias...
Suponiendo que NP! = CoNP, entonces no hay un certificado de tamaño polinómico para el problema de coNP completo. ¿Pero qué pasa con el certificado de tamaño subexponencial? Particularmente para coSAT, ¿hay una prueba de tamaño subexponencial para demostrar que una fórmula no es satisfactoria? Si...
Los parámetros fijos y la aproximación son enfoques totalmente diferentes para resolver problemas difíciles. Tienen motivaciones diferentes. La aproximación busca un resultado más rápido con una solución aproximada. El parámetro fijo busca una solución exacta con complejidad de tiempo en términos...
Cada vez que enseño NP-Completeness, los estudiantes preguntan "¿hay algún problema que se sepa que no pertenece a NP?" ¿Cómo responderías? Por lo general, les doy un problema indecidible como ejemplo, pero esto a menudo no resulta bien: (a) si les doy el problema de detención, piensan que es un...