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
Me interesan dos preguntas sobre los lenguajes sensibles al contexto (CSL) y la integridad: ¿Existe una noción de integridad para CSL y qué idiomas están completos? ¿Hay CSL naturales que son NP completas? Para 2., ciertamente puedo pensar en lenguajes NP-completos naturales que son CSL (como...
Según un resultado clásico de Kuroda, la clase de complejidad NSPACE [ ]nortenorten (también conocida como NLIN-SPACE) es precisamente la clase CSL de lenguajes sensibles al contexto . El problema de satisfacción SAT está en NSPACE [ ], ya que una suposición de tamaño lineal para una solución se...
A menudo consideramos clases de complejidad donde estamos limitados en la cantidad de espacio que nuestra máquina Turing puede usar, por ejemplo: o NSPACE ( f ( n ) ) . Parece que al principio de la teoría de la complejidad hubo mucho éxito con estas clases, como el teorema de la jerarquía espacial...
Savitch dio un algoritmo determinista para resolver la conectividad st usando el espacio , lo que implica N L ⊆ D S P A C E ( log 2 n ) . El algoritmo de Savitch se ejecuta en el tiempo 2 O ( log 2 n ) . Es un gran problema abierto si la conectividad st puede resolverse mediante un algoritmo...
SACiSUNCyoSAC^i es la clase de problemas de decisión que puede resolver una familia de circuitos de profundidad con compuertas OR sin límites y con compuertas AND con límites. Las negaciones solo están permitidas en el nivel de entrada. Se sabe que S A C i para i ≥ 1 está cerrado bajo el...
Gracias a Immerman y Szelepcsényi, se sabe que if (incluso para funciones construibles que no son espaciales).NSPACE(f)=coNSPACE(f)NSPACE(f)=coNSPACE(f){\rm NSPACE}(f)={\rm coNSPACE}(f)f=Ω(log)f=Ω(log)f=\Omega(\log) En el mismo documento, Immerman declara que la jerarquía alterna del espacio de...
Un MPA (autómata multipebble) es un 2DFA (autómata finito determinista bidireccional) que puede usar un número arbitrario de guijarros (en realidad, como máximo guijarros en una entrada dada - la entrada está escrita en la cinta entre dos extremos -marcadores como ). Durante el cálculo, un MPA...
Considere un vector dimensional donde . Para cada sabemos y supongamos que son independientes. Usando estas probabilidades, ¿hay una manera eficiente de iterar sobre vectores binarios dimensionales en orden de más probable a menos probable (con opciones arbitrarias para los lazos) usando el espacio...
El teorema de la jerarquía del tiempo establece que las máquinas de Turing pueden resolver más problemas si tienen (suficiente) más tiempo. ¿Se mantiene de alguna manera si el espacio está limitado asintóticamente? ¿Cómo se relaciona DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n),...
Estoy tratando de encontrar problemas cuya complejidad de espacio de casos promedio ha sido analizada. Más específicamente, estoy interesado en saber si hay algún problema con un límite inferior de complejidad espacial comprobada que sea superlineal, y especialmente si hay alguno con un análisis...
Pregunta general ¿El teorema de la jerarquía espacial se generaliza a la computación no uniforme? Aquí hay algunas preguntas más específicas: ¿Es ?L/poly⊊PSPACE/polyL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Para todas las funciones construibles en el espacio f(n)f(n)f(n) , ¿es...
Actualización: Parece que este problema ha sido estudiado y resuelto recientemente, vea este artículo wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton Y también esta encuesta: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Supongamos que, en lugar del conjunto habitual de...
Muestre una función que sea construible en el espacio pero no construible en el tiempo.f(n)f(n)f(n) ¿Está este problema relacionado con una posible separación entre las clases de complejidad DTIME (f (n)) y SPACE (f
Es bien sabido que el problema NP-Complete llamado Subset Sum tiene un FPTAS. Me preguntaba si existía un problema PSPACE Complete que también tiene un FPTAS. Gracias por
¿Los autómatas con límites lineales no deterministas de visita limitada reconocen solo los lenguajes normales? Por un autómata lineal no determinista (nLBA) me refiero a una máquina de Turing no determinista de una sola cinta donde la entrada viene "rellenada" con marcadores en ambos extremos que...
Teniendo en cuenta los números enteros positivos y correo , lo que se sabe sobre el espacio y el tiempo complejidad de encontrar el peso de Hamming (número de 1 binarios) de b correo ?sibbeeebebeb^e Si bits son disponibles, el número simplemente se puede calcular mediante técnicas estándar y los...
Un truco bien conocido para almacenar vectores de bits utilizando memoria no inicializada puede asignar un vector de bits de tamaño en el que todos los bits se ponen a asignando bits de memoria e inicializando solo de ellos. Esta representación admite la configuración y el desarmado de cualquier...
Considere el siguiente problema de decisión. Deje y deje que sea adecuado enumeración de aquellos subconjuntos de que tienen como máximo elementos.q=∑n/4i=0(ni)q=∑i=0n/4(ni)q = \sum_{i=0}^{n/4} \binom{n}{i}(Cn0,Cn1,…,Cnq−1)(C0n,C1n,…,Cq−1n)(C_0^n,
Considere una máquina (es decir, un algoritmo probabilístico que usa espacio de registro y polinomialmente muchos bits aleatorios). Se sabe (Saks-Zhou) que B P L ⊆ D S P A C E ( l o g 1.5 ( n ) ) .B PLsiPAGSLBPLB PL ⊆ D SPAGSA Cmi( l o g1,5( n ) )siPAGSL⊆reSPAGSUNACmi(losol1,5(norte))BPL \subseteq...