Sabemos que los solucionadores de SAT basados en DPLL no responden correctamente en casos insatisfactorios de (principio del agujero de paloma), por ejemplo, "hay un mapeo inyectivo de n + 1 a n ":P H PPAGHPAG\mathrm{PHP}n + 1norte+1n+1nortenorten P H Pn + 1norte: = ⎛⎝⋀i ∈ [ n + 1 ] ⋁j ∈ [ n...
Antecedentes Una fórmula de lectura única sobre un conjunto de compuertas (también llamada base) es una fórmula en la que cada variable de entrada aparece una vez. Las fórmulas de lectura única se estudian comúnmente sobre la base De Morgan (que tiene las compuertas de 2 bits AND y OR, y la...
Considere una colección de conjuntos F={F1,F2,…,Fn}F={F1,F2,…,Fn}F=\{F_1,F_2,\dotsc,F_n\} sobre un conjunto base U={e1,e2,…,en}U={e1,e2,…,en}U=\{e_1,e_2,\dotsc,e_n\} donde |Fi||Fi||F_i| ≪≪\ll nnn y ei∈Fiei∈Fie_i \in F_i , y sea kkk un número entero positivo. El objetivo es encontrar otra colección...
El sistema de prueba probabilística se conoce comúnmente como una restricción de M A , donde Arthur solo puede usar f ( n ) bits aleatorios y solo puede examinar g ( n ) bits de el certificado de prueba enviado por Merlin (ver, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP...
En general, estoy interesado en el método de forzamiento utilizado por Baker-Gill-Solovay y Cohen. Estoy buscando tantas fuentes como pueda tener en cuenta en relación con la técnica en sí o su uso. ¿Alguien tiene
Se sabe que minimizar el tamaño de una expresión regular es completo para PSPACE, incluso si tenemos un DFA como la especificación del lenguaje . ¿Cuáles son los resultados si el idioma es finito? Uno puede considerar este problema en dos modelos: La entrada es todas las cadenas en el idioma,...
Esperaba que alguien pudiera explicarme por qué exactamente el problema del producto del subconjunto es fuertemente NP-duro, mientras que el problema de la suma del subconjunto es débilmente NP-duro. Subconjunto Suma: Dada y , ¿existe un subconjunto tal que .X= { x1, . . . ,
Se ha realizado un trabajo fantástico en lo Permanente durante las últimas dos décadas. Me he estado preguntando por un tiempo sobre la posibilidad de un algoritmo Smooth P para el Permanente de Matrices No Negativas. Por supuesto, existe el famoso algoritmo JSV, pero este es un fpras. Pensando en...
El isomorfismo gráfico ( ) es un buen candidato para el intermedio . : existen problemas intermedios a menos que . Estoy buscando un problema natural que sea difícil para bajo la reducción de Karp (un problema de gráfico tal que ).GIGIGINPNPNPNPNPNPP=NPP=NPP=NPGIGIGIXXXGI<mpXGI<pmXGI...
¿Qué sucede si definimos P P A D dePPAD{\bf PPAD} tal manera que, en lugar de un circuito de polimerización de Turing-máquina / polisize, una máquina de Turing de espacio de registro o un circuito A C 0AC0{\bf AC^0} codifique el problema? Recientemente dando algoritmos más rápidos para...
FewP es la clase de problemas de N PNPNP con polinomios unidos en el número de soluciones (en el tamaño de entrada). Hay no se conoce N PNPNP problema -Complete en f e w PfewPfewP . Me interesa hasta dónde podemos extender esta observación. ¿Existe algún problema natural de N P-NPNP completo con...
En nuestro trabajo reciente, resolvemos un problema computacional que surgió en un contexto combinatorio, suponiendo que , donde es el -versión de . El único artículo sobre que encontramos fue el artículo de Beigel-Buhrman-Fortnow 1998 que se cita en Complexity Zoo . Entendemos que podemos tomar...
En forma simple: ¿Puede un autómata finito bidireccional reconocer gráficos vértice que contienen un triángulo con estados ?vvvo(v3)o(v3)o(v^3) Detalles Aquí son de interés los gráficos vértice codificados usando una secuencia de aristas, cada arista es un par de vértices distintos de...
En la complejidad del circuito, tenemos separaciones entre potencias de varios modelos de circuito. En la complejidad de la prueba, tenemos separaciones entre los poderes de varios sistemas de prueba. Pero en lo algorítmico, todavía tenemos pocas separaciones entre los poderes de los paradigmas...
¿Cuáles son algunos ejemplos importantes de desrandomización exitosa o al menos progreso en mostrar evidencia concreta hacia el objetivo (no la conexión de aleatoriedad de dureza)?PAG= B PPAGPAG=siPAGPAGP=BPP El único ejemplo que me viene a la mente es la prueba de primitiva de tiempo polinomial...
Estoy estudiando un problema que es difícil para la clase de fórmulas booleanas cuantificadas con un número logarítmico de alternancias de los cuantificadores. Un problema en esta clase se vería así: ∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalogn−1,…xalogn)F∀(X1,X2,...Xun1)∃(Xun1+1,...Xun2),...∃(XunIniciar...
Si está familiarizado con la verificación del programa, es probable que prefiera leer la Pregunta antes que los Antecedentes . Si no está familiarizado con la verificación del programa, es posible que aún pueda responder esta pregunta, pero es probable que prefiera leer el Fondo...
El teorema de Rice establece que cada propiedad no trivial del conjunto reconocida por alguna máquina de Turing es indecidible. Estoy buscando un teorema del tipo Rice de teoría de la complejidad que nos indique qué propiedades no triviales de los conjuntos de NP son
Dos documentos que incluiría son: D. Kozen, "Indización de clases subrecursivas" , STOC, 1978. R. Ladner, "Sobre la estructura de la reducibilidad del tiempo polinomial" , JACM,
El problema #SAT es el problema canónico # P-complete. Es un problema funcional más que un problema de decisión. Pregunta, dada una fórmula booleana en lógica proposicional, cuántas asignaciones satisfactorias tiene¿Cuáles son los mejores límites inferiores en