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...
Instancia: Un gráfico no dirigido con dos vértices distinguidos s ≠ t , y un entero k ≥ 2 .solGGs ≠ ts≠ts\neq tk ≥ 2k≥2k\geq 2 Pregunta: ¿Existe una ruta en G , de modo que la ruta toque a lo sumo k vértices? (La ruta toca un vértice si el vértice está en la ruta o tiene un vecino en la ruta).s -...
Una propiedad de gráfico se denomina hereditaria si se cierra con respecto a la eliminación de vértices (es decir, todas las subgrafías inducidas heredan la propiedad). Una propiedad gráfica se llama aditiva si se cierra con respecto a tomar uniones disjuntas. No es difícil encontrar propiedades...
Un problema importante en TCS es el problema de expresar un permanente como determinante. Estaba leyendo el artículo de Agrawal Determinante versus Permanente y en un párrafo afirma que el problema inverso es fácil. Es fácil ver que el determinante de una matriz se puede expresar como la...
¿ NPNP∩coNP=NPNPNP∩coNP=NP\mathsf{NP^{NP \,\cap\, coNP}=NP}mantener? Claramente NPNP≠NPNPNP≠NP\mathsf{NP^{NP}\neq NP} , pero me parece que NP∩coNPNP∩coNP\mathsf{NP\cap coNP} es "determinista", lo que me hace creer que esto es cierto. ¿Hay una prueba simple (o tal vez solo por definición)?...
Por lo tanto, una búsqueda rápida en la web me llevó a creer que "APXHardness implica que no existe QPTAS para un problema a menos que [alguna clase de complejidad] esté incluida en alguna [otra clase de complejidad]" y ¡también es bien conocido! Parece que todo el mundo lo sabe, excepto yo....
¿Podemos demostrar que para cada idioma que no es N P -duro (esto supone P ≠ N P ), P L ≠ P SAT ? Alternativamente, ¿se puede probar esto bajo cualquier supuesto razonable?L∈NPL∈NPL\in\mathsf{NP}NPNP\mathsf{NP}P≠NPP≠NP\mathsf P \ne \mathsf{NP}PL≠PSATPL≠PSAT\mathsf{P}^L \ne...
La página de Wikipedia en PSPACE menciona que la inclusión no es estricta (desafortunadamente sin referencias).NL⊂PHNL⊂PHNL\subset PH P1: ¿Qué pasa con y ? ¿Se sabe que son estrictos?L⊂PHL⊂PHL\subset PHL⊂P#PL⊂P#PL\subset P^{\#P} P2: Si no, ¿hay una clase establecida que contiene y para la cual no...
Tengo parte de un intento de prueba de . El intento de prueba consiste en una reducción de Karp desde -complete problem 3-REGULAR VERTEX COVER a SAT. ⊕ P ⊕⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}⊕P⊕P\oplus \mathbf{P}⊕⊕\oplus Dado un gráfico cúbico , la reducción genera una fórmula CNF que...
La entrada es un universo y una familia de subconjuntos de , por ejemplo, . Suponemos que los subconjuntos de pueden cubrir , es decir, .U F ⊆ 2 U F U ⋃ E ∈ F E = UUUUUUUF⊆ 2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃mi∈ Fmi= U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Una secuencia de cobertura incremental...
Sea una función booleana con sensibilidad s ( f ) y sensibilidad de bloque b s ( f ) .Fffs ( f)s(f)s(f)b s ( f)bs(f)bs(f) La conjetura de sensibilidad del bloque de sensibilidad establece que hay un tal que ∀ f , b s ( f ) ≤ s ( f ) c .c > 0c>0c>0∀ f, b s ( f ) ≤ s (...
La barrera de las pruebas naturales de Razborov y Rudich establece que, bajo supuestos criptográficos creíbles, uno no puede esperar separar NP de P / poli al encontrar propiedades combinatorias de funciones que son constructivas, grandes y útiles. Hay varios resultados bien conocidos que logran...
Estoy buscando una lista sobre la complejidad conocida o desconocida de varios problemas teóricos / algebraicos de números. Por ejemplo, El MCD en está abierto,NC1NC1NC^1 factoring en está abierto,PPP la cohomología informática de la gavilla es -duro#P#P\#P , Arora y Barak afirman que una...
¿Cuáles son algunas afirmaciones (no conocidas) de que si es cierto, el PH debe colapsar? Se agradecen las respuestas que contienen una afirmación corta de alto nivel con referencia (s). Traté de hacer una búsqueda inversa sin mucha
N P ⊆ P / p o l yP/poly=NP/polyP/poly=NP/polyP/poly = NP/poly implica , que a su vez tiene consecuencias interesantes como el colapso de la jerarquía polinómica.NP⊆P/polyNP⊆P/polyNP \subseteq P/poly ¿Hay implicaciones interesantes para ?P/poly≠NP/polyP/poly≠NP/polyP/poly \neq...
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...
La reducción de Karp es una reducción de tiempo polinómico computable de muchos entre dos problemas computacionales. Muchas reducciones de Karp son en realidad funciones uno a uno. Esto plantea la pregunta de si cada reducción de Karp es inyectiva (función uno a uno). ¿Existe un problema natural...
Me pregunto, ¿qué sucedería si en la definición de (Jerarquía polinómica, ver, por ejemplo, aquí ), el papel de N P fuera reemplazado por R P ?PHPHPHNPNPNPRPRPRP Parece, podríamos construir una jerarquía, del mismo modo que se construye, simplemente usando R P todas partes en lugar de N P y C O R...
Sea el tamaño mínimo de un circuito aritmético (no monótono) ( + , × , - ) que calcula un polinomio multilineal dado f ( x 1 , … , x n ) = ∑ e ∈ E c e n ∏ i = 1 x e i iA ( f)A(f)A(f)( + , × , - )(+,×,−)(+,\times,-) y B ( f ) denota el tamaño mínimo de uncircuitobooleano(no monótono) ( ∨ , ∧ , ¬...
Estoy considerando el lenguaje de todas las fórmulas lógicas proposicionales satisfactorias, SAT (para asegurarnos de que tenga un alfabeto finito, codificaríamos las letras proposicionales de alguna manera adecuada [editar: las respuestas señalaron que la respuesta a la pregunta puede no ser...