En una charla de Razborov, se publica una pequeña y curiosa declaración. Si FACTORING es difícil, entonces el pequeño teorema de Fermat no es demostrable en S12S21S_{2}^{1} . ¿Qué es S12S21S_{2}^{1} y por qué las pruebas actuales no están en S12S21S_{2}^{1} ?
En la complejidad de la comunicación, la conjetura de log-rank establece que cc(M)=(logrk(M))O(1)cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Donde cc(M)cc(M)cc(M) es la complejidad de comunicación de M(x,y)M(x,y)M(x,y) y rk(M)rk(M)rk(M) es el rango de MMM (como una matriz) sobre los...
¿Existe una clase natural de fórmulas de CNF, preferiblemente una que se haya estudiado previamente en la literatura, con las siguientes propiedades:CCC CCC es un caso fácil de SAT, como por ejemplo Horn o 2-CNF, es decir, la membresía en puede probarse en tiempo polinomial, y las fórmulas pueden...
Considere un lenguaje no vacío de cadenas binarias de longitud n . Puedo describir L con un circuito booleano C con n entradas y una salida de modo que C ( w ) sea verdadero si f w ∈ L : esto es bien conocido.LLLnortennLLLCCCnortennC( w )C(w)C(w)w ∈ Lw∈Lw \in L Sin embargo, quiero representar...
Se sabe que para el error la definición de peor caso de complejidad de comunicación aleatoria y la definición de caso promedio son equivalentes. Pero cuando el error es , la complejidad de comunicación aleatoria en el peor de los casos es la misma que la complejidad de comunicación...
La minimización de circuitos es el problema para minimizar el tamaño de un circuito dado. ¿Hay algo similar para los programas generales? En particular mi pregunta es: ¿Existen algoritmos para minimizar el número de instrucciones para un programa dado? Sé que es un problema indecidible, pero no...
Estoy interesado en el siguiente problema. Se nos da como entrada una "permutación de destino" , así como una lista ordenada de índices . Luego, comenzando con la lista (es decir, la permutación de identidad), en cada paso de tiempo intercambiamos el elemento en con el elemento, con probabilidad...
La hipótesis de Riemann de más de ½ siglo de antigüedad tiene profundas implicaciones en las matemáticas y ahora se prueba condicionalmente un gran edificio de teoría matemática y numerosas variantes. Recientemente encontré una referencia a un resultado condicional en TCS basado en la hipótesis de...
La complejidad de la prueba es un área más básica de la teoría de la complejidad computacional. Un propósito final de esta área es probar , es decir, cualquier comprobador no puede dar una prueba de insatisfacción de la fórmula de entrada dada. nortePAG≠ c o NPAGNP≠coNPNP\neq coNP Un gráfico es...
Siguiendo las preguntas equivalentes sobre NP-Completeness (ver la pregunta de peso y la pregunta dirigida ), me preguntaba cómo los problemas parametrizados se ven afectados por estos atributos. ¿Qué gráficos duros son -Hard en gráficos dirigidos, pero parámetros fijos manejables en gráficos...
¿Cuál es la complejidad del siguiente problema ( P? NP-hard?):∈∈\in Entrada: un gráfico acíclico dirigido , un conjunto de bordes hacia atrás E ' ⊂ V × V , y dos nodos distinta s y t .D=(V,E)D=(V,E)D=(V,E)E′⊂V×VE′⊂V×VE'\subset V\times Vsssttt Pregunta: Sea denotar la gráfica formada al agregar a...
Es un viejo problema abierto si un teorema de suma directa es válido para la complejidad de comunicación determinista, es decir, si resolver instancias independientes de un problema es t veces más difícil que resolver una sola instancia. [FKNN95] mostró los siguientes resultados:tttttt Un...
El teorema de Borsuk-Ulam dice que por cada función impar continua solsolg desde una esfera n al espacio n euclidiano, hay un punto X0 0X0 0x_0 tal que sol( x0 0) = 0sol(X0 0)=0 0g(x_0)=0 . Simmons y Su (2002) describen un método para aproximar el punto X0 0X0 0x_0 usando el lema de Tucker . Sin...
Considere el siguiente problema: Dada una matriz , queremos optimizar el número de adiciones en el algoritmo de multiplicación para calcular .v ↦ M vMMMv ↦ Mvv↦Mvv \mapsto Mv Este problema me parece interesante debido a su relación con la complejidad de la multiplicación de matrices (este...
Es bien sabido que ciertas clases de NP -Problemas Tienes dicotomía teoremas, lo que garantiza que todas las tareas en la clase es o NP -Complete o está en P . El mejor resultado conocido es el teorema de dicotomía de Schaefer , junto con una serie de generalizaciones. Entiendo que probar estos...
El problema parametrizado de k-FLIP SAT se define como: Entrada: una fórmula 3-CNF φφ\varphi con nortenorten variables y una asignación de verdad σ: [ n ] → { 0 , 1 }σ:[norte]→{0 0,1}\sigma : [n] \to \{0,1\} Parámetro: kkk Pregunta: ¿podemos transformar la asignación σσ\sigma en una asignación...
Deje que una máquina de Turing probabilística tenga acceso a una moneda injusta que sale cara con probabilidad (los lanzamientos son independientes). Defina B P P p como la clase de lenguajes reconocibles por dicha máquina en tiempo polinomial. Es un ejercicio estándar demostrar que:pagppB...
Supongamos que tengo un circuito booleano que calcula alguna función f : { 0 , 1 } n → { 0 , 1 } . Suponga que el circuito se compone de AND, OR y NO compuertas con entrada y salida de ventilador como máximo 2.CCCf: { 0 , 1 }norte→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\} Sea una entrada...
PREGUNTA CORTA: ¿MAJ-3CNF es un problema de PP completo bajo muchas reducciones? VERSIÓN MÁS LARGA: Es bien sabido que MAJSAT (decidir si la mayoría de las asignaciones de oración proposicional satisface la oración) es PP-completo bajo muchas reducciones y #SAT es # P-completo bajo reducciones...
¿El hecho de que un problema esté completo en el tiempo EXP implica que A no está en D T I M E ( 2 o ( n ) ) ?AAAAAADTIME(2o(n))DTIME(2o(n))DTIME(2^{o(n)}) Soy consciente de que, según el teorema de la jerarquía temporal, no está incluido en E = D T I M E ( 2 O ( n ) ) . Sin embargo, esto no...