Problemas com complexidade entre P e NP que possuem generalizações NP-completas

Alguém pode listar alguns problemas conhecidos que atendem às seguintes condições:

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. 

O mais famoso: gráfico isomorfismo e conjunto dominante em torneios.

Generalizações são naturais.

Outro natural: encontrar um equilíbrio de Nash (provavelmente) não é um NPC, mas encontrar um com alguma propriedade natural (por exemplo, que maximize a soma das utilidades dos jogadores) é o NPC. A prova original do NPC foi feita por Gilboa e Zemel no final dos anos 80 e, para uma referência recente, por exemplo, http://www.cs.duke.edu/~conitzer/nashGEB08.pdf

Vetor mais curto no problema de treliça, que é difícil de NP. A versão Gap GapSVP é intermediária:

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

A equivalência de dois sistemas de fecho finitos (famílias Moore) e J em um conjunto finito M . Onde K = { $\mathbb{K}$$J$$M$ é dado por um conjunto de subconjuntos de H e um grupo X é fechada sse pode ser obtido por um cruzamento de alguns conjuntos de K . O sistema de fechamento J = { A i → B i } é dado pelo conjunto de implicações e um conjunto X é fechado se respeitar todas as implicações de J, ou seja, para qualquer$\mathbb{K} = \{A_i \subseteq M \}$$M$$X$$\mathbb{K}$$J = \{A_i \rightarrow B_i\}$$X$$J$ se um i ⊆ X , em seguida, B i ⊆ X . A complexidade desse problema está aberta e sabe-se que esse problema é pelo menos difícil como a dualização de funções booleanas monótonas.$A_i\rightarrow B_i \in J$$A_i \subseteq X$$B_i \subseteq X$

Mas se considerarmos o problema: decida se o sistema de fechamento de é um subconjunto do sistema de fechamento de K, então não é difícil provar que esse problema se torna co-NP completo.$J$$\mathbb{K}$