en 1979 Hopcroft / Ullman escribió que L ⊆ P ⊆ NP ⊆ PSpace es conocido, pero L ⊊ PSpace es la única contención adecuada (y trivial) conocida, aunque se conjetura que todas son contenciones adecuadas, y "donde las cosas siguen en pie" ~ 4 décadas después . desde entonces, ¿hay alguna conexión...
Soy un estudiante de matemáticas interesado en TCS. Quiero estudiar por su cuenta los algoritmos y su complejidad para resolver los problemas teóricos grupales, como encontrar el orden de los elementos, enumeración de coset, encontrar generador, probar si un subconjunto determinado genera el...
Estoy buscando referencias bibliográficas para el siguiente algoritmo / problema: lo llamé "BiSelect" o "t-ary Select" o "Select in Union of Sorted Arrays", pero supongo que se introdujo antes con otro nombre. Problema Considere el siguiente problema: Dados kkk conjuntos ordenados disjuntos...
Podemos pensar en la complejidad de Kolmogorov de una cadena xxx como la longitud del programa más corto PPPy la entrada yyy tal que x=P(y)x=P(y)x = P(y) . Por lo general, estos programas se extraen de un conjunto completo de Turing (como PPP podría ser la descripción de una máquina de Turing, o...
Si es un gráfico con el máximo grado 3 y es un menor de H , entonces es un menor topológica de .solGGHHHHsolGGHHH Wikipedia cita este resultado de la "teoría de grafos" de Diestel. Está listado como la Proposición 1.7.4 en la última versión del libro. El libro carece de prueba o cita. ¿Se conoce...
Mientras respondía esta pregunta en teoría , demostré (informalmente) sobre la marcha el siguiente teorema: Teorema : para cualquier fija, la sonda del ciclo hamiltoniano permanece completa NP incluso si está restringida a gráficos bipartitos planos no direccionados de grado máximo 3 que no...
El SAT único es el problema bien conocido: dada una fórmula CNF , ¿es cierto que F tiene exactamente un modelo?FFFFFF Estoy interesado en el problema «Exactamente -SAT»: dada una fórmula F de CNF y un entero m > 1 , ¿es cierto que F tiene exactamente m modelos?mmmFFFm>1m>1m>1FFFmmm Ambos...
¡Entonces todos conocemos el límite inferior del árbol de comparación de en el peor de los casos de comparaciones realizadas por un algoritmo de clasificación de comparación (determinista). No se aplica a la clasificación de comparación aleatoria (si medimos las comparaciones esperadas para el peor...
Actualmente estoy haciendo una investigación de lenguaje formal que involucra clases de idiomas por encima de Regular pero debajo de Context Free. Estoy viendo cosas como máquinas multicontadores limitados por inversión, máquinas de contador de una sola pila, CFL deterministas, etc. Me pregunto si...
Estoy bastante seguro de que no soy el primero en considerar la idea que voy a presentar. Sin embargo, sería útil si puedo encontrar alguna literatura relacionada con la idea. La idea es construir una máquina de Turing M con la propiedad de que si P = NP, entonces M resolverá 3-SAT en tiempo...
Estoy tratando de entender a qué clase de complejidad pertenece el siguiente problema: Problema de raíz polinómica exponencial (EPRP) Sea un polinomio con deg ( p ) ≥ 0 con coeficientes extraídos de un campo finito G F ( q ) con q un número primo y r una raíz primitiva para ese campo. Determine...
¿Quién fue la primera persona en mostrar que un idioma está en NP si se puede verificar un certificado para el idioma en tiempo polinómico? ¿Tenemos un documento que lo demuestre formalmente? ¿Cuándo comenzó la comunidad TCS a desestimar el no determinismo en favor de la verificabilidad? No puedo,...
Hay investigadores que muestran que el bit de borrado tiene que consumir energía, ¿hay alguna investigación sobre el consumo promedio de energía del algoritmo con complejidad computacional ? Supongo que la complejidad computacional está correlacionada con el consumo promedio de energía, espero...
Leí el artículo de Freyd "Algebraically Complete Categories" en el famoso Como90 y tengo dos preguntas sobre la noción de compacidad algebraica que definió en ese artículo. (Si no está familiarizado con la definición, aquí está: una categoría se llama algebraicamente compacta si cada endofunctor...
Estoy leyendo encuestas de Trevisan y Lovett sobre aplicaciones de aditivo combinatorio en TCS. La mayoría de estas aplicaciones caen bajo la complejidad computacional , por ejemplo, límites inferiores. Me pregunto si la combinatoria aditiva también ha encontrado aplicaciones en el diseño de...
Digamos que un gráfico tiene la propiedad M si sus vértices se pueden ordenar v 1 , v 2 , ... v n de tal manera que el gráfico H i inducido por los vértices { v 1 , ... , v i } tiene d i s t H i ( v j , v k ) = d i s t G ( v j , vsolGGMETROMMv1, v2, ... vnortev1,v2,…vnv_1, v_2, \ldots v_nHyoHiH_i{...
Espero que alguien sepa algo sobre esto, así que no tengo que leer la literatura ... Considere una secuencia de números . Piense en la secuencia como n - 1 intervalos [ x 1 , x 2 ] , [ x 2 , x 3 ] , … , [ x n - 1 , x n ] . Claramente, la secuencia original es bitónica si algún punto en la línea...
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...
Si le dan una colección de órdenes parciales, la clasificación topológica le dirá si hay una extensión de la colección a una orden total (una extensión en este caso es una orden total consistente con cada una de las órdenes parciales). Me he encontrado con una variación: Fijar un conjunto . Te...
Dada compuesto N∈NN∈NN\in\Bbb N tamiz campo de número general es mejor algoritmo de factorización conocida para la factorización de enteros de NNN . Es un algoritmo aleatorio y obtenemos una complejidad esperada de