Agregue X como hipótesis, donde no se sabe que X sea verdadero o falso.
Al diseñar un algoritmo para un nuevo problema, si no puedo encontrar un algoritmo de tiempo polinómico después de un tiempo, podría intentar probar que es NP-hard en su lugar. Si tengo éxito, he explicado por qué no pude encontrar el algoritmo de tiempo polinómico. No es que sepa con certeza que...
En Complejidad descriptiva , Immerman tiene Corolario 7.23. Las siguientes condiciones son equivalentes: 1. P = NP. 2. Sobre estructuras finitas, ordenadas, FO (LFP) = SO. Esto puede considerarse como "amplificación" de P = NP a un enunciado equivalente sobre (presumiblemente) clases de...
Sabemos que L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} y que L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , donde L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . También sabemos que...
Según tengo entendido, el programa de teoría de la complejidad geométrica intenta separar al demostrar que el funcionamiento de una matriz de valores complejos es mucho más difícil de calcular que el determinante.VP≠VNPVP≠VNPVP \neq VNP La pregunta que tuve después de hojear los documentos de GCT:...
Complexity Zoo señala en la entrada de EXP que si L = P, entonces PSPACE = EXP. Dado que NPSPACE = PSPACE de Savitch, por lo que puedo decir, el argumento de relleno subyacente se extiende para mostrar que ( NL = P ) ⇒ ( PSPACE = EXP ) . (NL=P)⇒(PSPACE=EXP).(\text{NL} = \text{P}) \Rightarrow...
No se sabe que la factorización es NP-completa. Esta pregunta solicitó las consecuencias de que Factoring sea NP-completo. Curiosamente, nadie preguntó por las consecuencias de Factoring estar en P (tal vez porque esa pregunta es trivial). Entonces mis preguntas son: Cual seria el teorico...
Como aficionado de TCS, estoy leyendo material muy introductorio sobre informática cuántica. Aquí están los pocos datos elementales que he aprendido hasta ahora: No se sabe que las computadoras cuánticas resuelvan problemas NP-completos en tiempo polinómico. "La magia cuántica no será suficiente"...
En 1995, Russell Impagliazzo propuso cinco mundos de complejidad: 1- Algoritmica: con todas las asombrosas consecuencias.PAGS= NPAGSPAGS=nortePAGSP=NP 2- Heuristica: los completos de son difíciles en el peor de los casos ( ) pero se pueden resolver de manera eficiente en el caso...
Dos de los supuestos comunes para probar la dureza de los resultados de aproximación son y Unique Games Conjecture. ¿Hay alguna dureza de los resultados de aproximación suponiendo N P ≠ c o N P ? Estoy buscando el problema A tal que "es difícil aproximar A dentro de un factor α a menos que N P = c...
A menudo se cita una justificación filosófica para creer que P! = NP incluso sin pruebas. Otras clases de complejidad tienen evidencia de que son distintas, porque si no, habría consecuencias "sorprendentes" (como el colapso de la jerarquía polinómica). Mi pregunta es, ¿cuál es la base para creer...
Uno de los santos griales del diseño de algoritmos es encontrar un algoritmo fuertemente polinómico para la programación lineal, es decir, un algoritmo cuyo tiempo de ejecución está limitado por un polinomio en el número de variables y restricciones y es independiente del tamaño de la...
¿Cuáles serían las desagradables consecuencias de NP = PSPACE? Me sorprende no haber encontrado nada sobre esto, dado que estas clases se encuentran entre las más famosas. En particular, ¿tendría alguna consecuencia en las clases
Editar : como Ravi Boppana señaló correctamente en su respuesta y Scott Aaronson también agregó otro ejemplo en su respuesta , la respuesta a esta pregunta resultó ser "sí" de una manera que no esperaba en absoluto. Primero pensé que no respondían la pregunta que quería hacer, pero después de...
Esta pregunta se migró de Computer Science Stack Exchange porque se puede responder en Teorematic Computer Science Stack Exchange. Migrado hace 6 años . Parece que muchas personas creen que , en parte porque creen que la factorización no es solucionable por tiempo
Parity-L es el conjunto de lenguajes reconocidos por una máquina de Turing no determinista que solo puede distinguir entre un número par o un número impar de rutas de "aceptación" (en lugar de un número cero o no cero de rutas de aceptación), y que es restringido aún más al trabajo en espacio...
¿Conoces consecuencias interesantes de conjeturas (estándar) en la teoría de la complejidad en otros campos de las matemáticas (es decir, fuera de la informática teórica)? Preferiría respuestas donde: la conjetura de la teoría de la complejidad es lo más general y estándar posible; También...
RP es la clase de problemas que puede resolver una máquina de Turing no determinista que termina en tiempo polinómico, pero también se permite un error unilateral. P es la clase habitual de problemas que puede resolver una máquina de Turing determinista que termina en tiempo polinómico. P = RP se...
¿Cuáles son las consecuencias de tener problemas completos en ?nortePAGS∩ c o NPAGSNP∩coNPNP\cap
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
Si bien el teorema de Adleman muestra que , no conozco ninguna literatura que investigue la posible inclusión de B Q P ⊆ P / poly . ¿Qué consecuencias teóricas de la complejidad tendría tal inclusión?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP}...