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,...
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
Leí acerca de NPC y su relación con PSPACE y deseo saber si los problemas de NPC se pueden resolver de manera determinista utilizando un algoritmo con el requisito de espacio polinomial en el peor de los casos, pero potencialmente tomando tiempo exponencial (2 ^ P (n) donde P es...
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...
Tengo un problema y supongo que es NP-hard, pero no puedo probarlo. Aquí hay un gráfico de capas, donde la capa 0 es la capa más alta y la capa L la más baja. hay un borde dirigido entre capas, donde un borde (A, B) indica que el nodo A puede [cubrir] el nodo B. Y cuando A puede cubrir B, cada...
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...
Tomo curso sobre Complejidad Computacional. Mi problema es que no entiendo el método de relativización . Intenté encontrar un poco de intuición en muchos libros de texto, desafortunadamente, hasta ahora sin éxito. Apreciaré si alguien pudiera arrojar luz sobre este tema para poder continuar por mí...
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...
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} =
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...
Esta pregunta es algo opuesta a una pregunta anterior sobre conjuntos formados a partir de operaciones de conjuntos en conjuntos completos de NP: Si el conjunto resultante de la unión, intersección, o el producto cartesiano de dos conjuntos decidibles y es NP-completo, es decir, al menos uno de...
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...
¿El 2 en un algoritmo de aproximación 2 significa que la solución está dentro de 2 * OPT u OPT /
Así que acabamos de aprender sobre la auto-reducibilidad en clase. Mi profesor y nuestro libro de texto no se comprometerían a decir que todos los problemas en NP son auto reducibles, pero no parece haber ningún ejemplo de problemas que no lo sean. Me preguntaba si hay algún ejemplo, o si es solo...
¿Hay alguna clase de problemas NP que tengan una solución única? Lo pregunto porque cuando estaba estudiando criptografía leí sobre la mochila y la idea me pareció muy
Mi pregunta es la siguiente. Suponga que es un problema NP-hard. Dada una instancia arbitraria de y suponiendo que un adversario sabe que esta instancia es fácil de resolver, ¿es posible encontrar un algoritmo determinista de tiempo polinómico para resolver esta instancia particular...
Recientemente he pensado la siguiente prueba de que L = P implica P = NP. Supongamos que L = P. Deje que A sea un problema en NP. Según la definición del verificador de NP, cada solución positiva a A tiene un testigo que puede verificarse en tiempo polinómico. Como P = L, la misma solución se...
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...
Entonces significa problemas en los que tenemos pequeños testigos verificables para instancias de y para pequeños testigos verificables para instancias de . ¿Cómo funciona esto paraNPNPNPYESYESYEScoNPcoNPcoNPNONONO PNPPNPP^{NP} NPNPNPNPNP^{NP} coNPNPcoNPNPcoNP^{NP} ¿y
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