P vs NP: ejemplo instructivo de cuándo se puede evitar la búsqueda de fuerza bruta

Para poder explicar el problema P vs NP a los no matemáticos, me gustaría tener un ejemplo pedagógico de cuándo se puede evitar la búsqueda de fuerza bruta. Idealmente, el problema debería ser inmediatamente comprensible y el truco no debería ser ni demasiado fácil ni demasiado difícil.

Lo mejor que he encontrado hasta ahora es

SUBSET_PRODUCT_IS_ZERO

El problema es fácil de entender (dado un conjunto de enteros, ¿se puede formar un subconjunto con el producto 0?), Pero el truco es demasiado fácil (verifique si 0 está entre los números dados, es decir, no es necesario observar muchos subconjuntos).

¿Alguna sugerencia?

¡Recomiendo a Jenga !

$3N$$\Theta(N)$$N$$6N$$N^{\Theta(N)}$

Pero, de hecho, Uri Zwick demostró en 2005 que puedes jugar a Jenga perfectamente haciendo un seguimiento de solo tres enteros, usando un conjunto simple de reglas que puedes colocar fácilmente en una tarjeta de visita. Los tres números que necesitas son

• $m =$
• $n =$
• $t =$

$n\bmod 3$$m\bmod 3$$n$$m$

Aquí II significa que debe mover el ladrillo central de cualquier capa superior de 3 capas, II- significa que debe mover un ladrillo lateral de 3 capas a la parte superior, -I- significa que debe mover un ladrillo lateral de una capa de 2 capas arriba, y el bob-omb significa que debes pensar en la muerte y ponerte triste y esas cosas . Si hay más de un movimiento sugerido en un cuadro, puede elegir cualquiera de ellos. Es trivial ejecutar esta estrategia en tiempo si ya conoce el triple , o en tiempo si no lo sabe.$O(1)$$(m,n,t)$$O(N)$

Moraleja: Jenga solo es divertido si todos son torpes y / o borrachos.

Un cajero tiene que devolver centavos de cambio a un cliente. Dadas las monedas que tiene disponibles, ¿puede hacerlo y cómo?$x$

• Fuerza bruta: considere todas las colecciones posibles de monedas y vea si una de ellas suma .$x$
• Fuerza no bruta: hágalo como todos los cajeros, mediante programación dinámica.

Hay dos variantes del problema:

1. Fácil : el cajero tiene un suministro ilimitado de todas las denominaciones.
2. Más difícil: el cajero tiene un suministro limitado de monedas.

La variante fácil se puede resolver con un algoritmo codicioso. El más difícil requiere programación dinámica.

En realidad, la forma de presentar esto es proponer la solución de fuerza bruta, hacer que la gente entienda que es muy ineficiente y luego preguntarles qué hacen los cajeros, primero por la variante fácil, luego por la difícil. Debería tener algunos ejemplos disponibles que van de fácil a desagradable.

¡Creo que encontré un ejemplo útil yo mismo!

Quizás era un poco vago, pero estaba buscando un problema que cumpliera con las siguientes especificaciones:

• El problema en sí debería ser fácil de explicar a alguien que estudia ciencias sociales.
• Debería tener un algoritmo obvio pero ineficaz.
• Debería tener un algoritmo mejor que también sea fácil de explicar a alguien que estudie ciencias sociales.

Para el Ciclo Euleriano es fácil explicar que es una condición necesaria que cada nodo debe tener un grado uniforme, pero no es tan fácil explicar por qué es una condición suficiente.

Este es el problema que creo que hasta ahora cumple mejor con la especificación anterior:

FORM_TARGET_SET_WITH_UNIONS

Colección de conjuntos$C=\{S_1, S_2,...,S_n\}$

Conjunto de objetivos$T$

Pregunta: ¿Es posible formar el conjunto de objetivos tomando la unión de algunos de los conjuntos en ?$T$$C$

Algoritmo obvio pero ineficaz:

• Forme todas las uniones posibles$2^n$
• Vea si uno de ellos corresponde a$T$

Mejor algoritmo

• Marque los conjuntos en que están contenidos en$C$$T$
• Forme la unión de estos conjuntos$S_{_\cup}$
• Siresponda , de lo contrario responda$|S_{_\cup}|=|T|$$YES$$NO$

También está el problema de la hermana.

FORM_TARGET_SET_WITH_INTERSECTIONS

para lo cual el mejor algoritmo es

• Marque los conjuntos en que contienen$C$$T$
• Forme la intersección de estos conjuntos$S_{_\cap}$
• Siresponda , de lo contrario responda$|S_{_\cap}|=|T|$$YES$$NO$

Como puede ver, estaba buscando algo realmente simple (casi tan simple como SUBSET_PRODUCT_IS_ZERO).

El problema también se puede contrastar con SUBSET SUM y SUBSET PRODUCT, que son NP completos pero similares en su formulación. En todos estos problemas, se le presenta una colección de objetos y se le pregunta si una operación en una selección de estos objetos puede producir el resultado deseado.