Es bien sabido que la complejidad de distinguir un moneda sesgada de una feria es θ ( ε - 2 ) . ¿Hay resultados para distinguir una moneda p de una moneda p + ϵ ? Puedo ver que para el caso especial de p = 0 , la complejidad será ϵ - 1 . Tengo el presentimiento de que la complejidad dependerá de si...
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....
¿Se sabe si el problema de evaluación del circuito está en ? ¿Qué tal (uniform )? N C 1 A L o g T i m e N C 1NC1NC1\mathsf{NC^1}NC1NC1\mathsf{NC^1}ALogTimeALogTime\mathsf{ALogTime}NC1NC1\mathsf{NC^1} Sabemos que los circuitos de profundidad pueden evaluarse con circuitos de profundidad donde...
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...
Recientemente, estaba revisando una introducción a los algoritmos holográficos. Encontré algunos objetos combinatorios llamados Pfaffians. No sé mucho sobre eso en este momento y encontré algunos usos sorprendentes a los que se les puede dar. Por ejemplo, llegué a saber que se pueden usar para...
Se sabe que si , la jerarquía polinómica se colapsa en y .N P ⊆ P / P o l y Σ P 2 M A = A MNP⊆P/PolyNP\subseteq P/PolyΣP2\Sigma_2^{P}MA=AMMA = AM ¿Cuáles son los colapsos más fuertes que suceden si ?N E X P ⊆ P / P o l yNEXP⊆P/PolyNEXP\subseteq
Adleman ha demostrado en 1978 que BPP⊆P/polyBPP⊆P/poly\mathrm{BPP}\subseteq \mathrm{P/poly} : si una función booleana fff de nnn variables puede calcularse mediante un circuito booleano probabilístico de tamaño MMM , entonces fff también puede calcularse mediante un circuito booleano determinista...
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...
Sea la función mayoritaria, es decir, si y solo si . Me preguntaba si había una prueba simple del siguiente hecho (por "simple" me refiero a no confiar en el método probabilístico como Valiant 84 o en redes de clasificación; preferiblemente proporcionando una construcción explícita y directa del...
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...
A lo que me refiero como contar es el problema que consiste en encontrar el número de soluciones para una función. Más precisamente, dada una función F: N→ { 0 , 1 }F:norte→{0 0,1}f:N\to \{0,1\} (no necesariamente caja negra), aproximada # { x ∈ N∣ f( x ) = 1 } = | F-...
El ancho de árbol y el ancho de ruta son parámetros populares, que miden la cercanía de un gráfico a un árbol o una ruta, respectivamente. De hecho, parece que el ancho de árbol es tan popular que aparece en muchos documentos, libros y notas de conferencias que ofrecen (incluso muy suaves)...
La jerarquía es una jerarquía de clases de complejidad en complejidad parametrizada, consulte el Zoo de Complejidad para ver las definiciones. Una definición alternativa define usando la definibilidad ponderada de Fagin para las lógica de primer orden, vea el libro de texto de Flum y Grohe...
Parity-L, también conocido como L, 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". Niel de Beaudrap hizo una pregunta relacionada reciente .⊕⊕\oplus Mi pregunta es la...
Hay varios conocidos AC0AC0\mathsf{AC^0} de límite inferior de tamaño de circuito basados en restricciones aleatorias y el Lema de conmutación . ¿Podemos desarrollar un resultado de Lema de conmutación para probar un tamaño de límite inferior para circuitos TC0TC0\mathsf{TC^0} (similar a las...
En su artículo seminal Algoritmos teóricos grupales para multiplicaciones matriciales , Cohn, Kleinberg, Szegedy y Umans presentan el concepto de rompecabezas único y solucionable (definido a continuación) y la capacidad de USP. Afirman que Coppersmith y Winograd, en su innovador papel Matrix...
La eliminación gaussiana hace que el determinante de una matriz de tiempo polinómico sea computable. La reducción de la complejidad en la computación del determinante, que de otro modo es la suma de términos exponenciales, se debe a la presencia de signos negativos alternativos (la falta de lo que...
La fórmula más pequeña conocida para el determinante tiene un tamaño acuerdo con el folclore (o Ran Raz en su papel Las fórmulas multilineales para permanente y determinante son de tamaño superpolinomial ).norteO (logn )norteO(Iniciar sesiónnorte)n^{\mathcal O(\log n)} ¿Tienes alguna referencia...
Un algoritmo de prueba de distribución para una propiedad de distribución P (que es solo un subconjunto de todas las distribuciones sobre [n]) puede acceder a las muestras de acuerdo con alguna distribución D, y se requiere que decida (whp) si D∈PD∈PD\in P o d(D,P)>ϵd(D,P)>ϵd(D,P)>\epsilon (...
Conocemos el problema de contar el número de asignaciones satisfactorias en una fórmula booleana general dada (CNF-SAT), una fórmula DNF dada, o incluso una fórmula 2SAT dada es un problema # P-completo . Ahora, considere un CNF-SAT sin literal negativo (no , siempre A ). El problema de decisión...