Digamos que un lenguaje LLL está cerca de la densidad P si hay un algoritmo de tiempo polinómico que decide correctamente LLL en casi todas las entradas. A∈A∈A\in LΔALΔAL\Delta Alimn→∞|(LΔA)∩{0,1}n|2n=0.limn→∞|(LΔA)∩{0,1}n|2n=0.\lim_{n\rightarrow\infty} \frac{|(L\Delta A) \cap...
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...
En complejidad parametrizada, ⊆ W [ 2 ] . Se conjetura que cada una de las contenciones es adecuada.F P T ⊆ W [1]FPT⊆W[1]\mathsf{FPT} \subseteq \mathsf{W}[1] ⊆ W [ 2 ]⊆W[2]\subseteq \mathsf{W}[2] ⊆ ... ⊆ W [ P]⊆…⊆W[P]\subseteq \ldots \subseteq \mathsf{W}[P] Si entonces .P = W [ P ]F P T = W...
Recuerde que π(n)π(n)\pi(n) el número de primos ≤n≤n\le n es la función de recuento de primos . Por "PRIMES en P", calcular π(n)π(n)\pi(n) está en #P. ¿Es el problema # P-completo? O, tal vez, ¿hay una razón compleja para creer que este problema no es # P-completo? PD: Me doy cuenta de que esto...
Discusión : Últimamente he pasado algo de tiempo personal aprendiendo varias cosas en la complejidad de la comunicación. Por ejemplo, me he re-familiarizado con el capítulo relevante en Arora / Barak, comencé a leer algunos documentos y ordené el libro a Kushilevitz / Nisan. Intuitivamente, quiero...
El siguiente problema interesante surgió en mi investigación recientemente: INSTANCIA: Gráfico .G ( V, E)G(V,E)G(V, E) SOLUCIÓN: Una finalización de ciclo impar sin acordes, definida como un superconjunto del conjunto de bordes E, de modo que el gráfico completado G ' ( V , E ' ) tiene la...
¿Qué tan rápido debería ser un algoritmo no determinista para un problema completo EXPTIME para implicar ? Un algoritmo no determinista de tiempo polinómico implicaría esto inmediatamente porque pero nadie cree que . Si he hecho el álgebra a la derecha (ver más abajo), el teorema de la jerarquía...
En esta pregunta , parece que hemos identificado un problema natural que es NP completo bajo reducciones aleatorias, pero posiblemente no bajo reducciones deterministas (aunque esto depende de qué suposiciones no comprobadas en la teoría de números sean verdaderas). ¿Hay algún otro problema...
El Theoem de Karp-Lipton establece que si , entonces P H colapsa a Σ P 2 . Por lo tanto, suponiendo separaciones entre Σ P 2 y Σ P 3 , ningún problema completo de N P pertenecerá a P / p o l y .NP⊂P/polyNP⊂P/poly\mathsf{NP} \subset
Actualmente estoy interesado en obtener (o construir) y estudiar fórmulas 3-CNF que son insatisfactorias y de tamaño mínimo. Es decir, deben consistir en la menor cantidad posible de cláusulas (m = 8 preferiblemente) y la menor cantidad posible de variables distintas (n = 4 o más), de modo que...
¿Cómo diseñarías una imagen para ilustrar la conjetura de los juegos únicos? Esto es para una presentación de "Eventos actuales" sobre juegos únicos en la próxima reunión conjunta de AMS y para el folleto que se producirá. Ejemplos del tipo de ilustraciones producidas en el pasado están...
Según el relato histórico (no verificado), Kolmogorov pensó que cada lenguaje en PP\mathsf{P} tiene una complejidad de circuito lineal. (Vea la pregunta anterior conjetura de Kolmogorov que PPP tiene circuitos de tamaño lineal .) Tenga en cuenta que esto implica P≠NPP≠NP\mathsf{P}\neq \mathsf{NP}...
Estoy interesado en la complejidad de resolver ecuaciones lineales módulo k , para k arbitrario (y con un interés especial en las potencias primarias), específicamente: Problema. Para un sistema dado de ecuaciones lineales en incógnitas módulo , ¿existe alguna solución?n kmmmnnnkkk En el...
Supongamos que es el peor tiempo de ejecución de un problema en una entrada de tamaño . Hagamos el problema un poco extraño arreglando para pero para .f(n)f(n)f(n)nnnf(n)=n2f(n)=n2f(n) = n^2n=2kn=2kn=2kf(n)=nf(n)=nf(n) = nn=2k+1n=2k+1n=2k+1 Entonces, ¿cuál es el límite inferior del problema? La...
Actualmente, el cálculo de los reales en los idiomas más populares todavía se realiza a través de operaciones de coma flotante. Por otro lado, teorías como la efectividad de tipo dos (TTE) y la teoría de dominios han prometido durante mucho tiempo el cálculo exacto de los reales. Claramente, el...
La paridad y son como gemelos inseparables. O eso parece durante los últimos 30 años. A la luz del resultado de Ryan, habrá un renovado interés en las clases pequeñas.A C0 0AC0AC^0 Furst Saxe Sipser a Yao a Hastad son todas paridades y restricciones aleatorias. Razborov / Smolensky es un polinomio...
¡Predecir el mercado de valores es difícil! ¿Puede TCS hacer este sentimiento más formal? Recientemente comencé a pensar un poco sobre las finanzas y me preguntaba cómo podría ayudar el conocimiento de TCS. Los fondos de cobertura y las empresas de inversión parecen utilizar el comercio...
Deje ser una función de valor entero tal que esté en . ¿Se sigue que2 F # P F # PFFF2 F2F2F# P#P\#PFFF está en ? ¿Hay razones para creer que es poco probable que esto se cumpla siempre? ¿Alguna referencia que deba saber?# P#P\#P Sorprendentemente, esta situación surgió (con una constante mucho...
¿Hay alguna referencia que proporcione detalles sobre los límites inferiores del circuito para problemas difíciles específicos que surgen en la criptografía, como la factorización de enteros, el problema de logaritmo discreto primario / compuesto y su variante sobre el grupo de puntos de curvas...
EDITAR el 2011/02/08: Después de encontrar y leer algunas referencias, decidí separar la pregunta original en dos. Aquí está la parte relativa a UP vs NP, para la parte de clases sintácticas y semánticas, consulte Beneficios para clases sintácticas y semánticas . (el tiempo polinómico...