Es bien sabido que los palíndromos se pueden reconocer en tiempo lineal en máquinas Turing de cintas, pero no en máquinas Turing de cinta única (en cuyo caso el tiempo necesario es cuadrático). El algoritmo de tiempo lineal usa una copia de la entrada y, por lo tanto, también usa un espacio...
¿Cuál es la complejidad más conocida para calcular la distancia de edición exacta entre dos cadenas de la misma longitud utilizando un espacio de trabajo que es sublineal en el tamaño de la entrada? Supongo que la entrada se almacena en algún formato de solo lectura. ¿Es este un problema...
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 (...
Considere un lenguaje LLL tal que: L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) y asi que L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) En otras palabras, la máquina más...
Estoy interesado en la historia temprana de los resultados publicados sobre compensaciones de espacio-tiempo de propósito general. En particular, quiero saber quién describió por primera vez el siguiente tipo de algoritmo para evaluar un cálculo que tiene un gráfico de flujo de datos arbitrario con...
(ya preguntado en el sitio principal , pero preguntando también aquí por una mejor cobertura, lo siento) Como conocía las estructuras de datos sucintas, necesito desesperadamente una buena visión general de los desarrollos más recientes en esa área. Busqué en Google y leí muchos artículos que...
¿Puede el no determinismo acelerar el cálculo determinista? Si es así, ¿cuánto? Al acelerar el cálculo determinista por el no determinismo me refiero a los resultados de la forma: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Por ejemplo, algo...
Después de la discusión sobre los límites inferiores para 3SAT [ 1 ], me pregunto cuáles son los principales resultados del límite inferior formulados como compensaciones espacio-tiempo. Estoy excluyendo resultados como, por ejemplo, el teorema de Savitch; una buena entrada se centraría en un solo...
Si nos dan dos cadenas de tamaño y n 2 , la Levenshtein cálculo de distancia de edición estándar es mediante un algoritmo dinámico con el tiempo complejidad O ( n 1 n 2 ) y el espacio complejidad O ( n 1 n 2 ) . (Se pueden hacer algunas mejoras en función de la distancia de edición d , pero no...
Ha habido algunas preguntas ( 1 , 2 , 3 ) sobre la terminación transitiva aquí que me hicieron pensar si algo como esto es posible: Supongamos que obtenemos un gráfico solGG entrada dirigido y nos gustaría responder consultas del tipo " ?", Es decir, preguntar si existe un borde entre dos...
Este es un seguimiento de la aceleración no determinista del cálculo determinista . ¿Es plausible que el no determinismo (o una alternancia más general) permitiría una aceleración cuadrática general de la computación determinista? ¿O hay consecuencias inverosímiles conocidas para algo como...
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...