Actualmente estoy escribiendo una encuesta sobre teoremas de jerarquía en TCS. Al buscar artículos relacionados, noté que la jerarquía es un concepto fundamental no solo en TCS y matemáticas, sino en numerosas ciencias, desde teología y sociología hasta biología y química. Al ver que la cantidad de información es enorme, espero poder pedir ayuda a esta comunidad. Por supuesto, no quiero que hagas una búsqueda bibliográfica por mí, sino que te pido dos tipos de información:
Jerarquías y teoremas de jerarquía que son el resultado de su trabajo o el trabajo de sus colegas u otras personas con las que está familiarizado y cree que no son tan conocidas. Esto podría ser, por ejemplo, un teorema de jerarquía para un oscuro modelo de cálculo que le interese o una jerarquía de clases específicas, por ejemplo, relacionadas con la teoría de juegos.
Las jerarquías y los teoremas de jerarquía que considere absolutamente necesarios para ser incluidos en una encuesta de este tipo. Probablemente ya lo sé, pero sería útil ver qué jerarquías considera más importantes y por qué. Esto podría ser del tipo "Considero que el muy importante porque sin él no podríamos hacer este tipo de investigación" o "Aunque no es tan conocido, en TCS basados en lógica usamos constantemente esta jerarquía y creo que es una herramienta importante ". . Y sí, creo que las personas lógicas tienen muchas jerarquías que mencionar, sin embargo, tenga en cuenta que estamos hablando de jerarquías de problemas.
Mantendré una lista actualizada aquí:
- Jerarquía
- Jerarquía
- Jerarquía
- Jerarquía aritmética (también conocida como Kleene)
- Jerarquía hiperaritmética
- Jerarquía analítica
- Jerarquía Chomsky
- Jerarquía de Grzegorczyk y lo relacionado: jerarquía de Wainer (crecimiento rápido), jerarquía de Hardy
(crecimiento lento) y la jerarquía de Veblen - Jerarquía de Ritchie
- Jerarquía de Axt (como se define en Axt63 )
La jerarquía de bucles (definida en MR67 )
A C A C CJerarquía ( , )
- La jerarquía de profundidad, como se define en Sipser83
- Jerarquía polinómica ( ) y la jerarquía Meyer-Stockmeyer menos refinada (sin distinción entre cuantificadores)
- Jerarquía exponencial ( )
-Jerarquía intermedia (teorema de Ladner)
El no tan fuerte (Arthur-Merlin)
- La jerarquía (parámetro fijo no determinista) y la jerarquía W alternante relacionada (jerarquía ) y jerarquía (W con profundidad dependiente del parámetro)A W W ∗
- Jerarquía de conteo
- Jerarquía de Fourier
- Jerarquía booleana (sobre ), también igual a la Jerarquía de consultas (sobre )N P
- Jerarquías para pruebas de propiedad, como se ve en GoldreichKNR09
- La jerarquía de profundidad de punto de los lenguajes regulares sin estrellas
- d : las clases que se pueden resolver mediante programas de ramificación de tamaño polinómico, con la condición adicional de que cada bit de la entrada se pruebe en la mayoría de las veces d, forman una jerarquía para diferentes valores de
- La jerarquía de tiempo para la complejidad del circuito
- La jerarquía polinómica en la complejidad de la comunicación.
Nota: Si no desea ser mencionado exclusivamente, dígalo. Como regla general, mencionaré tanto a la comunidad como a la persona específica que saca a la luz nueva información.
Respuestas:
La Jerarquía de Fourier como se define en " Yaoyun Shi, Quantum y las compensaciones clásicas ".
Desde el complejo zoológico :
fuente
- A lo largo de las líneas de "anti-jerarquías", vale la pena mencionar el teorema de brecha de Borodin .
Esto contradiría el teorema de la jerarquía de tiempo, excepto que no es construible en el tiempo (de hecho, es por eso que debemos tener suposiciones de constructibilidad en las declaraciones de la mayoría de las jerarquías de complejidad).g
- También hay fortalecimientos interesantes de las jerarquías de tiempo habituales, como:
(hay problemas en el tiempo no se puede resolver con éxito en cualquier momento máquina del tiempo usando bits de consejos, incluso para infinitas longitudes de entrada). La prueba es fácil: deje que enumere las máquinas de tiempo que toman bits de consejos como una segunda entrada. Defina que divide en donde, ejecuta y genera la respuesta opuesta. Entonces .nk nk−1 n−logn {Mi} nk−1 n−logn M′(x) x x=yz |z|=log|x| Mz(x,y) L(M′)∉i.o.−TIME[nk−1]/(n−logn)
- La falta de jerarquías de tiempo conocidas en ciertas situaciones debe considerarse (como problemas abiertos). Por ejemplo, ¿es ?BPTIME[n]=BPP
fuente
El complejo zoológico le ofrece algunas jerarquías . Entre ellos, la Jerarquía de Conteo y la Jerarquía Booleana aún no fueron citados.
[EDITAR] Para que mi respuesta sea más informativa, una definición rápida de la Jerarquía de conteo.
Entonces, en cuanto a la jerarquía polinómica, se define como .CH ⋃kCkP
La jerarquía de conteo fue definida por Wagner [Wag86]. Los enlaces a la teoría de los circuitos de umbral fueron descubiertos por Allender & Wagner [AW93]. Mucho más recientemente, Bürgisser [Bür09] también utilizó la jerarquía de conteo para relacionar el modelo de Valiant con la conjetura de Shub y Smale. En particular, demostró que la conjetura implica un límite inferior superpolinómico para lo permanente.τ τ
[Wag86] KW Wagner. La complejidad de los problemas combinatorios con una representación de entrada sucinta . Acta Mathematica 23 (3), 325-356, 1986.
[AW93] E. Allender y KW Wagner. Jerarquías de conteo: tiempo polinómico y circuitos de profundidad constante . Current Trends in Computer Science , 469-483, 1993.
[Bür09] P. Bürgisser. Al definir enteros y probar el circuito aritmético del límite inferior . Complejidad computacional 18 (1), 81-103, 2009.
fuente
Goldreich et. Alabama. tener teoremas de jerarquía para pruebas de propiedad:
También en el ECCC .
fuente
Sipser mostró una jerarquía de profundidad dentro de , es decir, que los circuitos de profundidad de tamaño polivinílico son más potentes que los circuitos de profundidad de tamaño polivinílico:AC0 d+1 d
Sipser, conjuntos de M. Borel y complejidad del circuito . STOC 1983.
fuente
Dieter van Melkebeek y sus coautores tienen jerarquías de tiempo y espacio para modelos semánticos con consejos, incluida la aleatorización.
fuente
Aquí hay más jerarquías para clases semánticas con consejos. Específicamente, para ZPTIME y RTIME.
Lance Fortnow, Rahul Santhanam, Luca Trevisan. Jerarquías para Clases Semánticas . En STOC'05.
fuente
Existe la jerarquía Zheng-Weihrauch para números reales
X. Zheng y K. Weihrauch. La jerarquía aritmética de los números reales . Lógica Matemática Trimestral. Vol. 47 (2001), n. ° 1 51-65.
fuente
Hay una clase , definida en un artículo de 1975 por L. Adelman y K. Manders, que es un análogo diofantina de la clase . Un lenguaje está contenido en si existe un polinomio tal que Si es igual a es un problema abierto. Esta igualdad mostraría conexiones entre la teoría de números y la informática.D NP L D P
Existe un análogo diofantina de la jerarquía polinómica, llamada "jerarquía diofantina". Las jerarquías polinomiales y diofantinas están entrelazadas:
fuente
Otra jerarquía estricta: programas de ramificación que solo prueban cada bit un número limitado de veces. Cuantas más pruebas se permitan, mayor será la clase de programas de ramificación. Por lo general, los programas de ramificación también están restringidos al tamaño polinómico. BP d (P) es la clase de programas de ramificación de tamaño polinómico que pueden probar cada bit hasta veces.d
L / poly es la unión de BP d (P) sobre todo d , mientras que BP d-1 (P) BP d (P) para cada d .⊊
fuente
En la teoría de la complejidad parametrizada hay varias jerarquías, aunque solo la jerarquía ya mencionada aparece a menudo en las publicaciones. Otros son:W
Todos se describen en la teoría de complejidad parametrizada, Flum y Grohe, Birkhäuser, 2006 .
fuente
No estoy seguro si esto se ajusta a sus criterios, pero existe la jerarquía de profundidad de punto de los lenguajes regulares sin estrellas.
fuente
La jerarquía para el tamaño del circuito, ver pregunta anterior .
fuente
La teoría de las lenguas regulares de los árboles infinitos dio lugar a varias jerarquías, que actualmente se estudian, con muchas preguntas que aún están abiertas.
Cuando se usan autómatas en árboles infinitos, la condición de paridad (o condición de Mostowski) es de especial interés, porque los autómatas de paridad no deterministas pueden expresar todos los idiomas regulares de los árboles ininitas, y la estructura de la condición de aceptación es más simple que otras como Rabin o Müller .
Cada autómata de paridad tiene un rango donde e , que describe la estructura de la condición de aceptación. Por lo tanto, si un lenguaje es reconocible por un autómata (det / ND / alt) de rango , decimos que pertenece al nivel del (respectivamente):[i,j] i∈{0,1} i≤j L [i,j] L [i,j]
El nivel de la jerarquía alterna (es decir, es definible tanto por Büchi como por co-Büchi) corresponde al nivel débil y se caracteriza por autómatas alternos débiles, que dan lugar a una jerarquía:Σ2∩Π2 L
Para todas estas jerarquías (excepto la determinista), la capacidad de decidir la pertenencia a un nivel para un lenguaje regular dado es un problema abierto. Los vínculos entre estas jerarquías y clasificaciones topológicas (también llamadas jerarquía de Wadge y jerarquía de Borel) también plantearon varios problemas abiertos. Por ejemplo, se conjetura que la jerarquía de índice débil y la jerarquía de Borel coinciden. Se sabe que todas estas jerarquías son estrictas, y algunos casos especiales de decidir el nivel (especialmente los niveles bajos, o con el autómata determinista de entrada) se han resuelto recientemente.L
fuente
Existen jerarquías en la complejidad de prueba proposicional similares a las de la complejidad del circuito. Por , los sistemas de techo proposicionales son similares a , los sistemas a prueba de C-Frege para son similares a las clases de complejidad de circuito , y así sucesivamente.Gi PH C⊂P C
También hay jerarquías en aritmética limitada, por ejemplo , teorías , etc.Sij
fuente
Aquí hay una nueva jerarquía para lenguajes libres de contexto por Tomoyuki Yamakami.
Introduce un mecanismo de oráculo en autómatas pushdown no deterministas y nociones de Turing y reducibilidades de muchos. Luego, se construye una nueva jerarquía para lenguajes libres de contexto (CFL) similar a la jerarquía polinómica. Por ejemplo, , , etc. La parte interesante de todo esto es que se produce un colapso en la jerarquía de CFL si y solo si la jerarquía polinómica se colapsa.CFL CFLCFL
fuente
Desarrollando uno de los puntos mencionados por el OP (GoldreichKNR09): existen varios teoremas de jerarquía en pruebas de propiedad y pruebas de proximidad, relacionadas con la complejidad de la consulta, la adaptabilidad o la capacidad de prueba con respecto al número de rondas (para pruebas de proximidad). Ver, por ejemplo,
fuente
A partir de esta pregunta sobre cs.stackexchange , me di cuenta de la jerarquía de género de los lenguajes regulares . Esencialmente, puede caracterizar lenguajes regulares en función de la superficie mínima de género en la que puede incrustarse el gráfico de su DFA. En [1] se muestra que existen idiomas de género arbitrariamente grande y que esta jerarquía es adecuada.
fuente
Contando la jerarquía polinómica, #PH para abreviar. El primer nivel es #P luego #NP ... etc.
fuente
La Jerarquía Polinómica en la complejidad de la comunicación según lo definido por Babai, Frankl y Simon (ver el documento original aquí y sin el muro de pago aquí ). La importancia de esta jerarquía es difícil de sobreestimar. En primer lugar, BFS introdujo la función de desunión en el mismo documento que introdujo la jerarquía, y la desunión apareció de forma bastante natural como un problema completo de coNP . Como saben, la desunión es LA función en la complejidad de la comunicación. En segundo lugar, probar límites inferiores contra la jerarquía polinómica en la complejidad de la comunicación es un problema abierto importante con implicaciones importantes en otras áreas de TCS (por ejemplo, vea este documento y las referencias en él).cc
fuente
Considere la Jerarquía polinómica inequívoca, haga referencia aquí , referencia original aquí para la jerarquía polinómica inequívoca (con paredes de pago). Mientras estudiamos la jerarquía booleana BH , y clases como que tienen buenos resultados relacionados con el cierre, y establecen diferencias, podemos explorar conexiones a cálculos inequívocos.Dp
Como afirman los autores (en referencia original), las clases y dan resultados relacionados con y . Con un circuito inequívoco, podrían caracterizar diferente. Además, en relación con la jerarquía anterior está la jerarquía de promesa inequívoca. Resultados de baja para la jerarquía polinómica inequívoca: "si hay un conjunto de Turing escaso configurado para , la jerarquía se colapsa a niveles inferiores o en el caso no ambiguo de promesa".NCk ACk P PSPACE P UP
Relacionado para un mayor estudio de los conectivos booleanos, y el isomorfismo gráfico son las jerarquías baja y alta , también referencia de Wikipedia .
fuente
Más sobre el lado oscuro: mi teorema de jerarquía de segundo orden para lógicas de punto fijo en la teoría de modelos finitos. Ver otro teorema de la jerarquía .
fuente