Tengo una tarea para la cual me he estado golpeando la cabeza durante algún tiempo, y agradecería cualquier pista. Se trata de elegir un problema conocido, cuya integridad NP está probada, y construir una reducción de ese problema al siguiente problema que llamaré DGD (diagnóstico de gráfico...
Los ejemplos comunes de problemas NP-difíciles (camarilla, 3-SAT, cubierta de vértice, etc.) son del tipo en el que no sabemos si la respuesta es "sí" o "no" de antemano. Supongamos que tenemos un problema en el que sabemos que la respuesta es sí, además, podemos verificar un testigo en tiempo...
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...
Tengo un problema en mi mente, creo que es un problema NPC pero no sé cómo probarlo. Aquí está el problema: Hay k islas en un lago muy grande, y hay n pontones en forma de abanico. Esos pontones son del mismo tamaño pero tienen diferentes direcciones iniciales y están en diferentes posiciones...
Supongamos que ΠΠ\Pi es un problema de decisión decidible. ¿ Π∉NPΠ∉NP\Pi\not \in NP implica ΠΠ\Pi is NPNPNP -Hard? Editar: si suponemos que existe Π∈coNP∖NPΠ∈coNP∖NP\Pi\in coNP\setminus NP entonces hemos terminado. ¿Podemos refutar el reclamo sin suposiciones...
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...
Esta es una tarea del concurso de TI alemán ("Bundeswettbewerb Informatik"), pero dado que la fecha límite ha pasado, hacer esta pregunta no es trampa. Dado un gráfico dirigido ponderado por vértices y valores , encuentre un subconjunto de nodos que maximice sujeto a ¿Es este problema NP-hard?G =...
Estaba leyendo este documento donde los autores explican el Teorema 1, que establece que "Objeto alcanzable" (como se define en el documento) es NP-completo. Sin embargo, prueban la reducción solo en una dirección, es decir, desde 2P1N SAT hasta Objeto alcanzable. Esto solo prueba que el problema...