Problemas con la complejidad entre P y NP que tienen generalizaciones NP-completas

¿Alguien puede enumerar algunos problemas conocidos que satisfacen las siguientes condiciones:

1. has a generalization problem that is known to be NP-complete
2. has not been proved to be NP-complete nor has a known polynomial time solution. 

Más famoso: isomorfismo gráfico y conjunto dominante en torneos.

Las generalizaciones son naturales.

Otro natural: encontrar un equilibrio de Nash no es (probablemente) NPC, pero encontrar uno con alguna propiedad natural (por ejemplo, que maximiza la suma de las utilidades del jugador) es NPC. La prueba original de la APN fue realizada por Gilboa y Zemel a fines de los años 80, y para una referencia reciente ver, por ejemplo, http://www.cs.duke.edu/~conitzer/nashGEB08.pdf

Vector más corto en problema de celosía, que es NP difícil. La versión Gap GapSVP es intermedia:

http://en.wikipedia.org/wiki/Lattice_problem#Shortest_vector_problem_.28SVP.29

$\mathbb{K}$$J$$M$$\mathbb{K} = \{A_i \subseteq M \}$$M$$X$$\mathbb{K}$$J = \{A_i \rightarrow B_i\}$$X$$J$$A_i\rightarrow B_i \in J$$A_i \subseteq X$$B_i \subseteq X$

$J$$\mathbb{K}$