Problemy ze złożonością między P i NP, które mają uogólnienia NP-zupełne

Czy ktoś może wymienić niektóre dobrze znane problemy, które spełniają następujące warunki:

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. 

Najsłynniejsze: wykres izomorfizmu i dominacja w turniejach.

Uogólnienia są naturalne.

Kolejny naturalny: znalezienie równowagi Nasha nie jest (prawdopodobnie) NPC, ale znalezienie takiej z pewną naturalną właściwością (np. Która maksymalizuje sumę narzędzi gracza) to NPC. Oryginalny dowód NPC został napisany przez Gilboa i Zemela pod koniec lat 80., a najnowsze odniesienia można znaleźć np. Http://www.cs.duke.edu/~conitzer/nashGEB08.pdf

Najkrótszy wektor w problemie kratowym, który jest NP trudny. Wersja Gap GapSVP jest wersją pośrednią:

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}$