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 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} )...
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...
¿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 =
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...
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
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...
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...
Me pregunto esto basado en varios lugares en línea que llaman a co- un problema abierto importante ... pero no puedo encontrar ninguna indicación de si esto es lo mismo que Problema ...NP=NP=\sf NP=NPNP\sf NPP=NPP=NP\sf
Sé que es una tontería, pero logré confundirme y necesito ayuda para resolver esto Suponga que P=NPP=NPP=NP , entonces claramente para cada oráculo AAA tenemos PA=NPAPA=NPAP^A=NP^A que contradice el hecho de que existe algún oráculo AAA para el cual PA≠NPAPA≠NPAP^A\neq NP^A , de ahí P≠NPP≠NPP\neq...
Realmente me gustaría su ayuda para demostrar lo siguiente. Si entonces .NTime(n100)⊆DTime(n1000)NTime(n100)⊆DTime(n1000)\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})P=NPP=NP\mathrm{P}=\mathrm{NP} Aquí, es la clase de todos los idiomas que puede decidir la máquina de Turing no...
Hace poco leí una entrada de blog realmente interesante del Blog de Google Research sobre redes neuronales. Básicamente usan estas redes neuronales para resolver varios problemas como el reconocimiento de imágenes. Utilizan algoritmos genéticos para "evolucionar" los pesos de los...
Si , entonces es ? Estoy haciendo esta pregunta porque, para otras clases no deterministas, parece que siempre establece que son iguales a sus contrapartes deterministas.P=NPP=NP\mathbf{P} = \mathbf{NP}L=NLL=NL\mathbf{L} = \mathbf{NL}P=NPP=NP\mathbf{P} =
Estoy tratando de argumentar que N no es NP igual usando teoremas de jerarquía. Este es mi argumento, pero cuando se lo mostré a nuestro maestro y después de la deducción, dijo que esto es problemático cuando no puedo encontrar una razón convincente para aceptar. Comenzamos asumiendo que . Luego...
Valiant y Vazirani probaron que SAT es reducible a SAT ÚNICO bajo reducciones probabilísticas aleatorias en tiempo polinómico. Calabro y col . demostró que k-SAT ÚNICO es tan difícil como k-SAT. Ahora la pregunta es, si alguien muestra que k-SAT ÚNICO está en P, ¿implica P = NP? Referencias LG...
Quisiera su ayuda para probar que el lenguaje es decidible iff .L={⟨M⟩|L(M)∈NP∖P}L={⟨M⟩|L(M)∈NP∖P}L=\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \}P=NPP=NP\mathrm{P}=\mathrm{NP} Si , entiendo que es el lenguaje de las máquinas de Turing vacías. Entonces es un...
Tal vez me estoy perdiendo algo obvio, pero ¿puede ser que P = co-NP ⊊⊊\subsetneqNP o viceversa? Mi sensación es que debe haber algún teorema que descarte esta