Probleme mit der Komplexität zwischen P und NP, die NP-vollständige Verallgemeinerungen haben

Kann jemand einige bekannte Probleme auflisten, die die folgenden Bedingungen erfüllen:

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. 

Am bekanntesten: Graph Isomorphism und Dominating Set on Tournaments.

Verallgemeinerungen sind natürlich.

Ein anderes natürliches Problem: Das Finden eines Nash-Gleichgewichts ist (wahrscheinlich) kein NPC, aber das Finden eines Gleichgewichts mit einer natürlichen Eigenschaft (z. B. die die Summe der Dienstprogramme des Spielers maximiert) ist ein NPC. Der Original-NPC-Beweis stammt von Gilboa und Zemel in den späten 80er Jahren. Eine aktuelle Referenz finden Sie beispielsweise unter http://www.cs.duke.edu/~conitzer/nashGEB08.pdf

Kürzester Vektor im Gitterproblem, der NP-schwer ist. Die Gap-Version von GapSVP ist mittelschwer:

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

Die Äquivalenz von zwei endlichen Verschlusssystemen (Moore Familien) und J auf einem endlichen Menge M . Wobei K = { A i ⊆ M } durch die Menge von Teilmengen von M gegeben ist und eine Menge X geschlossen ist, wenn sie durch eine Schnittmenge einiger Mengen von K erhalten werden kann . Das Verschlusssystem J = { A i → B i } ist durch die Menge der Implikationen gegeben, und eine Menge X ist geschlossen, wenn es alle Implikationen von J respektiert, dh für ein beliebiges $\mathbb{K}$$J$$M$$\mathbb{K} = \{A_i \subseteq M \}$$M$$X$$\mathbb{K}$$J = \{A_i \rightarrow B_i\}$$X$$J$ , wenn A i ⊆ X dann B i ⊆ X . Die Komplexität dieses Problems ist offen und es ist bekannt, dass dieses Problem zumindest so schwer wie die Dualisierung von monotonen Booleschen Funktionen ist.$A_i\rightarrow B_i \in J$$A_i \subseteq X$$B_i \subseteq X$

Aber wenn wir das Problem betrachten: Entscheiden Sie, ob das Verschlusssystem von eine Teilmenge des Verschlusssystems von K ist, dann ist es nicht schwer zu beweisen, dass dieses Problem co-NP-vollständig wird.$J$$\mathbb{K}$