Problèmes de complexité entre P et NP qui ont des généralisations NP-complètes

Quelqu'un peut-il énumérer des problèmes bien connus qui remplissent les conditions suivantes:

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. 

Plus célèbre: Graph isomorphism, and Dominating Set on Tournaments.

Les généralisations sont naturelles.

Un autre naturel: trouver un équilibre de Nash n'est pas (probablement) un PNJ, mais en trouver un avec une propriété naturelle (par exemple, qui maximise la somme des utilitaires du joueur) est un PNJ. La preuve originale du PNJ a été réalisée par Gilboa et Zemel à la fin des années 80, et pour une référence récente, voir, par exemple, http://www.cs.duke.edu/~conitzer/nashGEB08.pdf

Vecteur le plus court dans le problème de réseau, qui est NP difficile. La version Gap GapSVP est intermédiaire:

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$. La complexité de ce problème est ouverte et il est connu que ce problème est au moins aussi dur que la dualisation des fonctions booléennes monotones. si A i ⊆ X alors B i ⊆ $A_i\rightarrow B_i \in J$$A_i \subseteq X$$B_i \subseteq X$

Mais si l'on considère le problème: décider si le système de fermeture de est un sous-ensemble du système de fermeture de K alors pas difficile de prouver que ce problème devient co-NP-complet.$J$$\mathbb{K}$