En otro hilo , Joe Fitzsimons preguntó sobre "los mejores límites inferiores actuales en 3SAT". Me gustaría ir a otro lado: ¿Cuál es el mejor límite superior actual en 3SAT? En otras palabras, ¿cuál es la complejidad temporal del solucionador SAT más eficiente? En particular, ¿es concebible...
Esta es una pregunta sobre la complejidad del circuito. (Las definiciones están en la parte inferior). Yao y Beigel-Tarui mostraron que cada familia de circuitos de tamaño tiene una familia de circuitos equivalente de tamaño de profundidad dos , donde la puerta de salida es una función simétrica y...
Usando el algoritmo carry look ahead podemos calcular la suma usando una familia de circuitos tamaño de polinomio de profundidad 5 (o 4?) . ¿Es posible reducir la profundidad? ¿Podemos calcular la suma de dos números binarios usando una familia de circuitos de tamaño polinómico con una profundidad...
Entiendo que la integridad de Turing requiere memoria ilimitada y tiempo ilimitado. Sin embargo, hay una cantidad finita de átomos en este servicio, lo que limita la memoria. Por ejemplo, aunque es irracional, no hay forma de almacenar más de un cierto número de dígitos, incluso si todos los...
Deje que G sea un árbol en 2n vértices. El ancho de árbol de G, tw (G) = 1. Ahora supongamos que agregamos n aristas a G para obtener un gráfico H. Un límite superior fácil en tw (H) es n + 1. ¿Es esto esencialmente el mejor posible? Parece de alguna manera que tw (H) debería ser O (sqrt (n)),...
Considere el siguiente modelo de circuito monótono simple: cada puerta es solo un OR binario. ¿Cuál es la complejidad de una función f ( x ) = A xf(x)=Axf(x)=Ax donde AAA es una matriz booleana n × nn×nn \times n con O ( n )O(n)O(n) 0? ¿Se puede calcular mediante circuitos OR de tamaño lineal? Más...
Me gustaría saber el estado actual de la transición de fase para k-sat aleatorio, dadas n variables y m cláusulas, cuál es la c = m / n más conocida para los límites superior e
Supongamos que consideramos 3-SAT con vvv variables y cláusulas . Estoy investigando un método que parece tomar tiempo / espacio para resolver cualquier problema SAT que se ajuste a esta descripción, dentro de un error que se puede ajustar a una cantidad arbitraria. Sin embargo, hay una trampa.O (...
¿Es un problema CNF SAT NP difícil cuando el número total (pero no el ancho) de las cláusulas de 3 o más términos está limitado por una constante? ¿Qué pasa específicamente cuando solo hay una de esas
Deje para , con la promesa de que (donde la suma ha terminado ). Entonces, ¿cuál es la complejidad de determinar si ?xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\}i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\}x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\}ZZ\mathbb{Z}x=1x=1x = 1 Observe que...
Defina como un gráfico dirigido al azar ( vértices; colocamos el borde entre dos vértices con probabilidad ).n pG(n,p)G(n,p)G(n, p)nnnppp ¿Cuáles son los resultados conocidos para el siguiente problema? Fijar dos vértices vvv y uuu . ¿Cuál es la probabilidad de que haya al menos una ruta (de...