Preguntas sobre recursos espaciales de cálculos en complejidad computacional o algoritmos.
Esta podría ser una pregunta subjetiva en lugar de una con una respuesta concreta, pero de todos modos. En teoría de la complejidad estudiamos la noción de cálculos eficientes. Hay clases como representa el tiempo polinómico y representa el espacio de registro . Se considera que ambos están...
Defina LOGLOG como la clase de lenguajes que se pueden calcular en el espacio O (loglog n) mediante una máquina de Turing determinista (con acceso bidireccional a la entrada). De manera similar, defina NLOGLOG como la clase de lenguajes que se pueden calcular en el espacio O (log log n) mediante...
ST-conectividad es el problema de determinar si existe un camino dirigido entre dos vértices distinguidos y t en un gráfico dirigido G ( V , E ) . Si este problema se puede resolver en el espacio de registro, es un problema abierto de larga data. Esto se llama el N L vs L
En primer lugar, me disculpo de antemano por cualquier estupidez. De ninguna manera soy un experto en teoría de la complejidad (¡lejos de eso! Soy un estudiante universitario que toma mi primera clase en teoría de la complejidad). Aquí está mi pregunta. Ahora el teorema de Savitch establece que...
Es bien sabido que la conectividad st dirigida es -completa. Consecuencia del avance Reingold mostró que no dirigido st-conectividad está en L . Planar dirigida st-conectividad es conocido por ser en U L ∩ c o U L . Cho y Huynh definen un problema de la mochila parametrizada y exhibieron una...
Está claro que cualquier problema que sea decidible en el espacio de registro determinista ( ) se ejecuta en la mayoría de los casos de polinomios ( ). Hay una gran cantidad de clases de complejidad entre y . Los ejemplos incluyen , , , , , . Se cree ampliamente que .P L P N L L o g C F L N C i S A...
El ancho del árbol mide qué tan cerca está un gráfico de un árbol. Es NP-difícil calcular el ancho del árbol. El algoritmo de aproximación más conocido logra factor.O(logn−−−−√)O(logn)O(\sqrt{{\log}n}) El teorema de Courcelle establece que cualquier propiedad de gráficos definibles en lógica...
Me pregunto si hay alguna justificación para creer que o para creer que ?N L ≠ LnorteL = LNL=LNL=LnorteL ≠ LNL≠LNL\neq L Se sabe que . La literatura sobre derandomization de es bastante convincente de que . ¿Alguien sabe acerca de algunos artículos o ideas convincentes que ? R L R L = L N L ≠...
Siguiendo con una pregunta anterior , ¿Cuáles son los mejores límites inferiores del espacio actual para SAT? Con un límite inferior de espacio, me refiero al número de celdas de cintas de trabajo utilizadas por una máquina de Turing que utiliza un alfabeto binario de cintas de trabajo. Un...
Considere el lenguaje .EQUALITY={anbn∣n≥0}EQUALITY={anbn∣n≥0} \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} Se sabe que no puede ser reconocido por ninguna máquina de Turing alterna (espacio) sublogarítmico (Szepietowski, 1994) . (¡Hay un cajero automático que utiliza un espacio sublogarítmico...
Immerman y Szelepcsenyi demostraron independientemente que . Usando su técnica de conteo inductivo, Borodin et al probaron que S A C i está cerrado bajo complementación, para i > 0 . Antes del teorema de Reingold ( S L = L ), Nisan y Ta-Shma demostraron S L = c o S L , utilizando reducciones de...
En general, la cinta de consulta para un oráculo cuenta para la complejidad espacial de una TM. Sin embargo, parece plausible permitir una cinta de oráculo de solo escritura (como la que se usa en las reducciones de espacio L). ¿Es útil esta construcción? ¿Produce algún resultado particularmente...
USTCONN es el problema que requiere decidir si hay una ruta desde el vértice de origen hasta el vértice de destino en un gráfico , donde todos estos se dan como parte de la entrada.ssstttGGG Omer Reingold demostró que USTCONN está en L (doi: 10.1145 / 1391289.1391291 ). La prueba construye un...
En un artículo clásico, Munro y Paterson estudian el problema de cuánto almacenamiento se requiere para que un algoritmo encuentre la mediana en una matriz ordenada aleatoriamente. En particular, se centran en el siguiente modelo: la entrada se lee de izquierda a derecha varias veces P. Se...
Recientemente, Watrous et al probaron que QIP (3) = PSPACE es un resultado notable. Este fue un resultado sorprendente para mí por decir lo menos y me hizo pensar ... Me preguntaba qué pasaría si las computadoras cuánticas pudieran ser simuladas eficientemente por computadoras clásicas. ¿Podría...
Hay una multitud de algoritmos que pueden analizar una gramática libre de contexto en tiempo . Usando la multiplicación de matrices, incluso se puede ir asintóticamente más rápido que eso.O ( n3)O(n3)O(n^3) Sin embargo, todos los algoritmos para analizar CFG arbitrarios que conozco tienen un uso...
Se dice que una distribución ϵ -engaña una función f si | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . Y se dice que engaña a una clase de funciones si engaña a todas las funciones de esa clase. Se sabe que la varepsilon espacios -biased engañar a la clase de las paridades sobre subconjuntos....
Es fácil ver que cualquier problema que sea decidible en el espacio de registro determinista ( ) se ejecuta en la mayoría de los casos de polinomios ( P ). Muchos algoritmos de espacio de registro conocidos (por ejemplo: conectividad st no dirigida, isomorfismo de gráfico plano) se ejecutan en O (...
El cálculo cuántico limitado en el tiempo es obviamente muy interesante. ¿Qué pasa con el cálculo cuántico limitado por el espacio? Conozco muchos resultados interesantes para la computación cuántica con límites de espacio sublogarítmico y varios tipos de modelos de autómatas cuánticos. Por otro...
Nisan demostró en "Generadores psuedoraaleatorios para la computación limitada al espacio", que existe un generador pseudoaleatorio que "engaña" las computaciones limitadas al espacio. ¿Esta construcción es válida para cada oráculo (al menos para consultas no