Preguntas sobre problemas de decisión que pueden resolverse en máquinas de Turing no deterministas en un polinomio temporal en la longitud de la entrada.
Hay muchos intentos de probar o , y, naturalmente, muchas personas piensan en la pregunta y tienen ideas para probar cualquier dirección.P ≠ N PP = N PPAGS=nortePAGS\mathsf{P} = \mathsf{NP} P ≠ N PPAGS≠nortePAGS\mathsf{P} \neq \mathsf{NP} Sé que hay enfoques que han demostrado que no funcionan, y...
Tengo una comprensión de alto nivel del problema y entiendo que si se "probara" absolutamente que es cierto con una solución provista, se abriría la puerta para resolver numerosos problemas dentro del ámbito de la informática.P=NPP=NPP=NP Mi pregunta es, si alguien publicara una prueba...
¿Hay problemas de NP completo que hayan probado algoritmos de tiempo subexponencial? Estoy solicitando las entradas de casos generales, no estoy hablando de casos especiales manejables aquí. Por sub-exponencial, me refiero a un orden de crecimiento por encima de los polinomios, pero menos que...
¿Hay algún problema conocido en N PNP\mathsf{NP} (y no en PAGSP\mathsf{P} ) que no sea N PNP\mathsf{NP} Complete? Tengo entendido que actualmente no hay problemas conocidos en este caso, pero no se ha descartado como una posibilidad. Si hay un problema que es NPNP\mathsf{NP} (y no PP\mathsf{P} )...
Un colega mío y yo acabamos de tocar algunas notas de uno de nuestros profesores. Las notas indican que hay tareas que son posibles de resolver en tiempo polinomial (están en la clase de PF) pero que NO son verificables en tiempo polinomial (NO están en la clase de NPF). Para elaborar sobre estas...
Cuando estaba explicando la prueba de Baker-Gill-Solovay de que existe un oráculo con el que podemos tener, , y un oráculo con el que podemos tener a un amigo, surgió una pregunta de por qué tales técnicas no son adecuadas para probar el problema , y no pude dar una respuesta satisfactoria.P ≠ N P...
A muchos se les ocurrió que en todas las pruebas de que he leído (que puedo recordar), siempre es trivial mostrar que hay un problema en , y mostrar que es -duro es la ... parte difícil. ¿Qué problemas -completos son estos cuyos verificadores de tiempo polinómico son altamente no...
Me gustaría comenzar la pregunta diciendo que soy programador y que no tengo muchos antecedentes en teoría de la complejidad. Una cosa que he notado es que si bien muchos problemas son NP completos, cuando se extienden a problemas de optimización, algunos son mucho más difíciles de aproximar que...
Entonces entiendo la idea de que el problema de decisión se define como ¿Existe una ruta P tal que el costo sea menor que C? y puede verificar fácilmente que esto sea cierto al verificar la ruta que recibe. Sin embargo, ¿qué pasa si no hay un camino que se ajuste a este criterio? ¿Cómo...
¿Es posible que y la cardinalidad de sea la misma que la cardinalidad de ? ¿O significa que y deben tener diferentes cardinalidades?P≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}P≠NPP≠NP\mathsf{P} \not =
El teorema de Galois dice efectivamente que no se pueden expresar las raíces de un polinomio de grado> = 5 usando funciones racionales de coeficientes y radicales. ¿No se puede leer que esto dice que dado un polinomio no hay un algoritmo determinista para encontrar las raíces? Ahora considere...
¿Ha habido alguna investigación sobre la complejidad de la prueba de una resolución al problema P = NP? Si no es así, dada la falta de progreso en el problema, ¿no sería razonable conjeturar que cualquier prueba que resuelva el problema P = NP requerirá un número súper polinómico de...
Si de hecho es igual a N P , ¿cómo mejoraría esto nuestros algoritmos para factorizar enteros más rápido? En otras palabras, ¿qué tipo de información nos daría este hecho para comprender mejor la factorización de enteros?PP{\sf P}NPNP{\sf
Estoy seguro de que alguien ha pensado en esto antes o lo descartó de inmediato, pero ¿por qué la teoría de la dicotomía de Schaefer junto con el teorema de Mahaney sobre conjuntos dispersos no implican P = NP? Aquí está mi razonamiento: crear un lenguaje que sea igual a SAT intersectado por un...
Esta es mi primera publicación después de ser un usuario pasivo desde hace algún tiempo. Deseo hacer algunas preguntas si puedo. No soy matemático pero mi pregunta se relaciona con el campo de las matemáticas / informática. En particular, el problema P vs NP. Soy consciente de que este es un...
Mi profesor hizo la declaración Cualquier problema finito no puede ser NP-Complete Estaba hablando de Sudoku en ese momento diciendo algo similar a que para un Sudoku 8x8 hay un conjunto finito de soluciones, pero no puedo recordar exactamente lo que dijo. Escribí la nota que he citado pero...
Vi en esta publicación en stackoverflow que hay algunos algoritmos relativamente rápidos para tamizar un intervalo de números para ver si hay un primo en ese intervalo. Sin embargo, ¿esto significa que el problema de decisión general de: (¿Existe una prima en un intervalo?) Está en P. (Hubo muchas...
Tengo esta "prueba" muy simple para NP = CoNP y creo que hice algo mal en alguna parte, pero no puedo encontrar lo que está mal. ¿Alguien me puede ayudar? Sea A un problema en NP, y sea M el decisivo para A. Sea B el complemento, es decir, B está en CoNP. Dado que M es un elemento decisivo,...
Soy consciente de que esto parece una pregunta muy estúpida (o demasiado obvia para decir). Sin embargo, estoy confundido en algún momento. Podemos mostrar que P NP=== si y solo si podemos diseñar un algoritmo que resuelva cualquier instancia dada de problema en NP en tiempo polinómico. Sin...
Esta es probablemente una pregunta estúpida, pero simplemente no entiendo. En otra pregunta se les ocurrió el teorema de dicotomía de Schaefer . Para mí, parece que demuestra que cada problema de CSP está en P o en NP-completo, pero no en el medio. Dado que cada problema de NP puede transformarse...