Sabemos que L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} y que L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , donde L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . También sabemos que...
¿Cuáles son los mejores límites inferiores actuales para el tiempo y la profundidad del circuito para
Permítanme comenzar con algunos ejemplos. ¿Por qué es tan trivial mostrar que CVP está en P pero tan difícil de mostrar que LP está en P? mientras que ambos son problemas P-completos. O toma la primalidad. Es más fácil mostrar compuestos en NP que primos en NP (que requirieron Pratt) y...
El libro de Arora y Barak presenta el factoring como el siguiente problema: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORIZACIÓN={⟨L,U,norte⟩El |(∃ un primer pags∈{L,...,U})[pagsEl |norte]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p...
La jerarquía de Chomsky (–Schützenberger) se usa en los libros de texto de informática teórica, pero obviamente solo cubre una fracción muy pequeña de lenguajes formales (REG, CFL, CSL, RE) en comparación con el Diagrama completo del zoológico de complejidad . ¿La jerarquía juega algún papel en la...
El teorema de Ladner establece que si P ≠ NP, entonces hay una jerarquía infinita de clases de complejidad que contienen estrictamente P y estrictamente contenidas en NP. La prueba utiliza la integridad de SAT bajo reducciones de muchos en NP. La jerarquía contiene clases de complejidad construidas...
Estoy buscando conjeturas sobre algoritmos y complejidad que muchos consideraron creíbles en algún momento, pero que luego fueron refutadas, o al menos no creídas, debido a la creciente evidencia contraria. Aquí hay dos ejemplos: Hipótesis de oráculo aleatorio: las relaciones entre clases de...
Siempre tuve problemas para comprender la importancia de la brecha de integralidad (IG) y sus límites. IG es la proporción de (la calidad de) una respuesta entera óptima a (la calidad de) una solución real óptima de la relajación del problema. Consideremos la cubierta de vértice (VC) como un...
Hablando informalmente, la complejidad de Kolmogorov de una cadena es la longitud de un programa más corto que genera x . Podemos definir una noción de 'cadena aleatoria' usándola ( x es aleatoria si K ( x ) ≥ 0.99 | x | ) Es fácil ver que la mayoría de las cadenas son aleatorias (no hay tantos...
Se sabe que el TSP métrico se puede aproximar dentro de y no se puede aproximar mejor que 1231,51.51.5 en tiempo polinomial. ¿Se sabe algo sobre la búsqueda de soluciones de aproximación en tiempo exponencial (por ejemplo, menos de2npasos con solo espacio polinómico)? Por ejemplo, ¿en qué tiempo y...
¿Alguien puede proporcionar una explicación concisa del enfoque GCT de Mulmuley comprensible para los no expertos? Una explicación que sería adecuada para una página de Wikipedia sobre el tema (que es un trozo en este momento). Motivación: estoy "co-leyendo" el libro de computación cuántica de...
¿Qué explicaciones teóricas existen para el éxito práctico de los solucionadores de SAT, y alguien puede dar una descripción y explicación "estilo wikipedia" uniéndolos a todos? Por analogía, el análisis suavizado ( versión arXiv ) para el algoritmo simplex hace un gran trabajo explicando por...
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...
Actualmente estoy escribiendo una encuesta sobre teoremas de jerarquía en TCS. Al buscar artículos relacionados, noté que la jerarquía es un concepto fundamental no solo en TCS y matemáticas, sino en numerosas ciencias, desde teología y sociología hasta biología y química. Al ver que la cantidad de...
Fondo El cálculo sobre números reales es más complicado que el cálculo sobre números naturales, ya que los números reales son objetos infinitos y hay innumerables números reales, por lo tanto, los números reales no pueden representarse fielmente por cadenas finitas sobre un alfabeto finito. A...
El problema del isomorfismo gráfico (IG) es posiblemente el candidato más conocido para un problema NP-intermedio . El algoritmo más conocido es el algoritmo sub-exponencial con tiempo de ejecución . Se sabe que GI no esNP-completo a menos que lajerarquía polinómica secolapse.2O ( n...
Deje que sea una tarea algorítmica. (Puede ser un problema de decisión o un problema de optimización o cualquier otra tarea). Llamemos a "en el lado polinomial" si se supone que es NP-hard implica que la jerarquía polinómica se colapsa. Llamemos a "en el lado NP" si se supone que admite que un...
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...
Esta es una publicación cruzada de math.stackexchange. Deje que FACT denote el problema de factorización de enteros: dado encuentre los primos y los enteros modo quep i ∈ N , e i ∈ N , n = ∏ k i = 0 p e i i .n ∈ N ,n∈N,n \in \mathbb{N},pagsyo∈ N ,pi∈N,p_i \in \mathbb{N},miyo∈ N ,ei∈N,e_i \in...
Deje que PRIMES (también conocido como prueba de primalidad ) sea el problema: Dado un número natural nnn , ¿es nnn un número primo? Deje que FACTORING sea el problema: Dados los números naturales , m con 1 ≤ m ≤ n , ¿ n tiene un factor d con 1 < d < m ?nnnmmm1≤m≤n1≤m≤n1 \leq m \leq...