La complejidad descriptiva clasifica los problemas en función de lo difícil que es expresar el problema con algún formalismo lógico.
El teorema de Immerman-Vardi establece que PTIME (o P) es precisamente la clase de lenguajes que puede describirse mediante una oración de lógica de primer orden junto con un operador de punto fijo, sobre la clase de estructuras ordenadas. El operador de punto fijo puede ser punto menos fijo (según...
El título más o menos lo dice todo, pero creo que podría agregar un poco de antecedentes y algunos ejemplos específicos que me interesan. Los teóricos de la complejidad descriptiva, como Immerman y Fagin, han caracterizado muchas de las clases de complejidad más conocidas utilizando la lógica. Por...
Parece que se sabe que para encontrar una respuesta a una consulta sobre una base de datos relacional , se necesita tiempo , y no se puede eliminar el exponente.QQQDDD|D||Q||D||Q||D|^{|Q|}|Q||Q||Q| Como puede ser muy grande, nos preguntamos por qué las bases de datos funcionan en la...
El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones: singleton: crea una lista con un elemento, le devuelve un puntero insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo...
El papel Lauri Hella y José María Turull-Torres, Cálculo de consultas con lógicas de orden superior , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 propone lógica VO, lógica de orden variable. Esto permite la cuantificación sobre los pedidos sobre las variables. VO es bastante...
CMSOL está contando la lógica monádica de segundo orden, es decir, una lógica de gráficos donde el dominio es el conjunto de vértices y bordes, existen predicados para la adyacencia vértice-vértice y la incidencia de borde-vértice, hay cuantificación sobre bordes, vértices, conjuntos de bordes y...
En esta pregunta , se mencionó que existen versiones descriptivas de complejidad del teorema de Rice. Encontré una prueba del siguiente teorema: Dada una clase de complejidad C , las propiedades no triviales de los lenguajes en C no se pueden calcular en C Anteriormente había publicado la...
Deje que π: { 0 , 1 }∗→ { 0 , 1 }∗π:{0,1}∗→{0,1}∗\pi \colon \{0,1\}^* \to \{0,1\}^* sea una permutación. Tenga en cuenta que mientras ππ\pi actúa en un dominio infinito, su descripción puede ser finita. Por descripción , me refiero a un programa que describe la funcionalidad de ππ\pi . (Como en...
Contexto: consideramos solo los dígrafos. Deje que CYCLE sea el lenguaje de gráficos con un ciclo; Es un problema de NL completo. Deje que HASEDGE sea el lenguaje de gráficos con al menos un borde. Entonces, trivialmente, CICLO ∪ HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup \text{HASEDGE} ya no es...
Es bien sabido que ciertas clases de NP -Problemas Tienes dicotomía teoremas, lo que garantiza que todas las tareas en la clase es o NP -Complete o está en P . El mejor resultado conocido es el teorema de dicotomía de Schaefer , junto con una serie de generalizaciones. Entiendo que probar estos...
En Complexity Zoo, dice [ 1 ] que, en complejidad descriptiva, PAGPAGP puede definirse mediante tres tipos diferentes de fórmulas, FO ( L FPAG)FO(LFPAG)FO(LFP) que también es FO ( nO ( 1 ))FO(norteO(1))FO(n^{O(1)}) , y también como SO ( HO R N)SO(HORnorte)SO(HORN) . Sin embargo, hay algunas...
Del teorema de Rice se deduce que no se puede determinar si dos máquinas de Turing deciden o no el mismo idioma. Mi pregunta es: ¿Esto también se aplica en configuraciones de complejidad descriptiva, particularmente cuando se trata de probar un par de consultas SO-Horn para ver si describen el...
Mi pregunta es acerca de la teoría del modelo finito / complejidad descriptiva, por lo que significará "primer orden sobre palabras binarias finitas, usando predicados Rs y un predicado unario P verdadero en la posición del 1 en la palabra".FO(R)FO(R)FO(R) Me gustaría saber, ¿hay alguna...
Estoy tratando de entender el documento sobre p-Optimal Proof Systems and Logic para PTIME . Hay una noción llamada sistemas de prueba en el documento y no entiendo: Σ={0,1}Σ={0 0,1}\Sigma = \{0,1\} ... Identificamos problemas con subconjuntos deQQQ enΣ∗Σ∗\Sigma^* . Creo que la intuición es...
Para comprender mejor un artículo, estoy tratando de obtener una breve comprensión de la lógica de punto menos fijo. Hay algunos puntos donde estoy atrapado. Si G = ( V, E)sol=(V,mi)G = (V,E) es un gráfico y Φ ( P) = { ( a , b ) ∣ G ⊨ E( a , b ) ∨ P( a , b ) ∨ ∃ z( E( a ,...
Cerrado. Esta pregunta está fuera de tema . Actualmente no está aceptando respuestas. ¿Quieres mejorar esta pregunta? Actualice la pregunta para que sea sobre el tema para el intercambio teórico de pila de informática. Cerrado hace 7 años . ¿Cómo...
No se cree que lo siguiente sea cierto: L⊆L−uniform NC1L⊆L−uniform NC1\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1 ¿Puedes ayudarme a ver dónde se rompe la discusión? El problema de accesibilidad dirigida está completo para . Sostengo que está en -uniform .L N C...
Es bien sabido en la teoría de modelos finitos que sin un orden en la entrada, la expresividad es muy limitada. Por ejemplo, se sabe que es igual a PSPACE , y F O ( PFP ) (sin ningún orden en la entrada) es solo PSPACE -relacional, una noción definida por Abiteboul y Vianu cuando demostraron su...