En el documento de Ben-Dor / Halevi [1] se da otra prueba de que el permanente es -completo. En la parte posterior del documento, muestran la cadena de reducción mientras el valor permanente se conserva a lo largo de la cadena. Como el número de asignaciones satisfactorias de una fórmula 3SAT se...
Estoy interesado en la historia temprana de los resultados publicados sobre compensaciones de espacio-tiempo de propósito general. En particular, quiero saber quién describió por primera vez el siguiente tipo de algoritmo para evaluar un cálculo que tiene un gráfico de flujo de datos arbitrario con...
¿Cuál es la complejidad computacional de optimizar varias funciones sobre el grupo unitario U(n)U(n)\mathcal{U}(n) ? Una tarea típica, que surgen a menudo en la teoría de la información cuántica, sería maximizar una cantidad de tipo (o superior polinomios de orden en U ) sobre toda unitaria...
Respuesta: no conocida. Las preguntas formuladas son naturales, abiertas y aparentemente difíciles; La pregunta ahora es una wiki comunitaria. Visión general La pregunta busca dividir los idiomas que pertenecen a la clase de complejidad PPP , junto con las máquinas de Turing de decisión (TM)...
¿Cuál es la complejidad de consulta más conocida del algoritmo de aprendizaje Goldreich-Levin? Las notas de la conferencia del blog de Luca Trevisan , Lemma 3, lo declaran como . ¿Es este el más conocido en términos de dependencia de ? ¡Estaré particularmente agradecido por una referencia a una...
Estoy buscando información sobre la complejidad computacional de la multiplicación de matrices de matrices rectangulares. Wikipedia afirma que la complejidad de multiplicar por B ∈ R n × p es O ( m n p ) (multiplicación del libro escolar).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in...
Estoy comenzando mi doctorado este otoño y estoy planeando trabajar en teoría de la complejidad para mi tesis. Estoy compilando una lista de documentos importantes que todo teórico de la complejidad debería saber. ¿Qué documentos le sugerirías a una persona como yo? Y explique brevemente por qué...
Mi primera pregunta es si la caracterización de un sistema de prueba interactivo es conocida para todas las clases de complejidad clásicas. Llamaría P, NP, PSPACE, EXP, NEXP, EXPSPACE, funciones recursivas y recursivamente enumerables clásicas (entre otras). Específicamente, ¿se conoce una...
Resultado 1: el teorema de Linial-Mansour-Nisan dice que el peso de Fourier de las funciones calculadas por los circuitos AC0AC0\mathsf{AC}^0 se concentra en los subconjuntos de pequeño tamaño con alta probabilidad. Resultado 2: El PARITYPARITY\mathsf{PARITY} tiene su peso de Fourier concentrado...
GI y Knot Problem, ambos son problemas para decidir la equivalencia estructural de los objetos matemáticos. ¿Hay algún resultado que establezca conexiones entre ellos? Se han explorado buenas conexiones del problema de nudos con la física estadística a través de polinomios de nudos , ¿hay...
¿Cuál es la clase de complejidad asociada con los algoritmos de búsqueda exhaustiva? (si hay uno) ¿Es NP o PSPACE? ¿Existen modelos restringidos de cómputo que capturen la clase de algoritmos de búsqueda exhaustiva similares a los modelos para programación codiciosa y
Dada como entrada un número entero nnn y un conjunto SSS de conjuntos de elementos de {1,...,n}{1,...,n}\{1, ..., n\} , ¿cuál es la complejidad de encontrar un conjunto TTT de elementos de {1,...,n}{1,...,n}\{1, ..., n\} tal que TTT tiene una cardinalidad mínima y TTT se incluye en ninguno de los...
A partir de los comentarios sobre una de mis preguntas sobre MathOverflow, tengo la sensación de que la pregunta sobre que GCD está en vs. es similar a la pregunta sobre la Factorización de enteros en vs. .NCNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}NPNP\mathsf{NP} ¿Hay algo así como un algoritmo...
Durante mucho tiempo, pensé que un problema era NP-completo si es (1) NP-hard y (2) está en NP. Sin embargo, en el famoso artículo "El método del elipsoide y sus consecuencias en la optimización combinatoria" , los autores afirman que el problema del número cromático fraccional pertenece a NP y...
Jan Pax hizo esta pregunta en la lista de correo de Fundamentos de Matemáticas . Ciertamente, P⊕P⊆P#P=PPPP⊕P⊆P#P=PPPP^{\oplus P} \subseteq P^{\#P} = P^{PP} pero sospecho por las respuestas a esta pregunta que no se sabe si ⊕P⊆PP⊕P⊆PP\oplus P \subseteq PP (de lo contrario, PPPPPP sería una posible...
Como todos saben, SAT está completo para wrt polinomial-tiempo muchas reducciones de uno. Todavía está completo wrt reducciones muchos-uno.N PnortePAG\mathsf{NP}A C0 0UNC0 0\mathsf{AC^0} Mi pregunta es ¿cuál es la profundidad mínima requerida para las reducciones? Más formalmente, ¿Cuál es la...
Estoy leyendo el apéndice sobre los límites inferiores de ACC para NEXP en el libro Arora and Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf Uno de los lemas fundamentales es una transformación de la circuitos a lo largo de los polinomios...
Busqué en Internet, pero no pude encontrar ninguna 'gran lista' de variantes del problema SAT. Aparte del (común) SE SENTÓ, k-SAT, MAX-kSAT, Medio SAT, XOR-SAT, NAE-SAT ¿Qué más variantes hay? (también será realmente útil si se dan clases de complejidad (cuando sea...
Lema: Suponiendo equivalencia eta tenemos eso (\x -> ⊥) = ⊥ :: A -> B. Prueba: ⊥ = (\x -> ⊥ x)por equivalencia eta y (\x -> ⊥ x) = (\x -> ⊥)por reducción bajo la lambda. El informe Haskell 2010, sección 6.2 especifica la seqfunción mediante dos ecuaciones: seq :: a -> b ->...
Se ha demostrado que la propagación de creencias es un método muy poderoso a través de la investigación en modelos gráficos probabilísticos. Sin embargo, no sé nada sobre BP que sea comparable a los métodos MCMC donde podemos tener esquemas de aproximación aleatoria totalmente polinomiales (FPRAS)...