Es bien sabido que no existe un protocolo determinista de dos partes puede resolver el problema de disyunción (DISJ) en entradas -bit sin enviar bits en el peor de los casos (véase, por ejemplo, el libro de Kushilevitz y Nisan). Para protocolos aleatorios de error acotado, Razborov [Razborov92]...
En su trabajo , Oráculos de distancia aproximada , Thorup y Zwick demostraron que para cualquier gráfico ponderado no dirigido, es posible construir una estructura de datos de tamaño que pueda devolver una distancia aproximada entre cualquier par de vértices en el gráfico.O ( k n1 + 1 /...
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...
Alice y Bob tienen cadenas de n bits, y quieren averiguar si son iguales mientras hacen poca comunicación. La solución aleatoria estándar es tratar las cadenas de n bits como polinomios de grado luego evaluar los polinomios sobre algunos elementos elegidos al azar de un campo de tamaño mayor que n...
Antecedentes : Estoy llegando al final de mi maestría en matemáticas y comenzaré un doctorado en lógica en agosto. Mientras más lógica estudio, más informática teórica estoy expuesta, por ejemplo, teoría de la recursión, cálculo lambda, pero el CS subyacente está debajo de la alfombra. Mis...
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...
Siendo de Física, he sido entrenado para investigar muchos problemas desde un punto de vista geométrico. Por ejemplo, la geometría diferencial de múltiples en sistemas dinámicos, etc. Cuando leo los fundamentos de la informática, siempre trato de encontrar interpretaciones geométricas. Como una...
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 ->...
Puede una máquina estándar de dos contadores ( ) con las siguientes instrucciones:c1,c2c1,c2c_1,c_2 1) ADD 1 to c_i, GOTO label_j 2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k 3) GOTO label_j 4) HALT and ACCEPT|REJECT decide el siguiente idioma: L={n2∣n≥1}L={n2∣n≥1}L = \{...
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)...
Dado un grafo, G=(V,E)G=(V,E)G = (V, E) , quiero encontrar un óptimo -domination para . Es decir, quiero un subconjunto de tal que todos los vértices enrrrGGGSSSVVVGGG están a una distancia de como máximo rrr de algún vértice en SSS , mientras se minimiza el tamaño de SSS . De lo que he verificado...
La proporción crítica de cláusulas a variables para el 3-SAT aleatorio es más de 3 y menos de 6, y parece describirse comúnmente como "alrededor de 4.2" o "alrededor de 4.25". Mezard, Parisi y Zecchina prueban (en el sentido de la física) que la relación crítica es 4.256, mientras que el primer y...
El problema del camino más largo es NP-hard. La prueba (¿típica?) Se basa en una reducción del problema del camino hamiltoniano (que es NP completo). Tenga en cuenta que aquí la ruta se considera simple (nodo). Es decir, ningún vértice puede ocurrir más de una vez en el camino. Obviamente, también...
Considere la siguiente configuración: se nos da una pila que contiene elementos.sssnnorten podemos usar un número constante de pilas adicionales.O(1)O(1)O(1) podemos aplicar las siguientes operaciones en estas pilas: comprobar si una pila está vacía compara los elementos principales de dos...
Mientras se discuten fuertes pruebas de normalización, este comentario contrasta el "modelo de formas normales" con los "métodos puramente sintácticos". Esto me lleva de vuelta a una pregunta más básica: ¿podemos distinguir estrictamente las construcciones sintácticas y semánticas, frente a los...
Se menciona en un comentario en otra publicación cstheorySE que la integridad de PSPACE implica dureza APX. ¿Alguien puede explicar / compartir una referencia para ello? ¿Es esto "apretado"? (es decir, ¿hay problemas completos de PSPACE cuyo problema de optimización admite una aproximación de...