<p>Another natural one: finding a Nash equilibrium is (likely) not NPC, but finding one with some natural property (e.g. that maximizes the sum of player utilities) is NPC.  The original NPC proof was by Gilboa and Zemel in the late 80s, and for a recent reference see, e.g., <a href="http://www.cs.duke.edu/~conitzer/nashGEB08.pdf">http://www.cs.duke.edu/~conitzer/nashGEB08.pdf</a></p>

CC BY-SA 3.0
2012-04-07T08:41:49.320Z
2012-04-07T08:41:49.320Z
Noam
<p>Shortest Vector in Lattice Problem, which is NP hard. The Gap version GapSVP is intermediate:</p>

<p><a href="http://en.wikipedia.org/wiki/Lattice_problem#Shortest_vector_problem_.28SVP.29">http://en.wikipedia.org/wiki/Lattice_problem#Shortest_vector_problem_.28SVP.29</a></p>

CC BY-SA 3.0
2012-04-09T21:35:55.703Z
2012-04-09T21:35:55.703Z
Mahdi Cheraghchi
<p>The equivalence of two finite closure systems (Moore families) $\mathbb{K}$ and $J$ on a finite set $M$. Where $\mathbb{K} = \{A_i \subseteq M \}$ is given by the set of subsets of $M$ and a set $X$ is closed iff it can be obtained by an intersection of some sets from $\mathbb{K}$. The closure system $J = \{A_i \rightarrow B_i\}$ is given by the set of implications and a set $X$ is closed iff it respects all implications from $J$ i.e. for any $A_i\rightarrow B_i \in J$ if $A_i \subseteq X$ then $B_i \subseteq X$. The complexity of this problem is open and it is known that this problem is at least hard as dualization of monotone boolean functions. </p>

<p>But if we consider the problem: decide if the closure system of $J$ is a subset of closure system of $\mathbb{K}$ then not hard to proof that this problem becomes co-NP-complete.</p>

CC BY-SA 3.0
2012-04-08T13:30:25.203Z
2012-04-08T13:30:25.203Z
Mikhail Babin
<p>Most famously: Graph Isomorphism, and Dominating Set on Tournaments.</p>

<p>Generalizations are natural.</p>

CC BY-SA 3.0
2012-04-06T05:55:30.167Z
In particular, one generalization of GI is subgraph isomorphism, which is NPC
Suresh Venkat
CC BY-SA 3.0
2012-04-05T17:17:40.877Z
2012-04-05T17:17:40.877Z
Yixin Cao
<p>Can anyone list some well-known problems that satisfies the following conditions:</p>

<pre><code>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. 
</code></pre>

CC BY-SA 3.0
2012-04-05T19:20:01.317Z
what do you mean by generation problem ?
Shiva Kintali
CC BY-SA 3.0
2012-04-05T22:27:09.853Z
Sorry, I meant generalization.
sma
<cc.complexity-theory><np-hardness>
Problems with complexity between P and NP that have  NP-complete generalizations
sma
# Problems with complexity between P and NP that have  NP-complete generalizations

(Asked by: username_0 on 2012-04-05)

Can anyone list some well-known problems that satisfies the following conditions:
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.

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_1**: what do you mean by generation problem ?  
> **username_0**: Sorry, I meant generalization.  

---

## 4 answers

### Answer by username_5 on 2012-04-05. Score: 18 | Accepted answer

Most famously: Graph Isomorphism, and Dominating Set on Tournaments.

Generalizations are natural.

> **Comments:**
> **username_6**: In particular, one generalization of GI is subgraph isomorphism, which is NPC  

---

### Answer by username_2 on 2012-04-07. Score: 14

Another natural one: finding a Nash equilibrium is (likely) not NPC, but finding one with some natural property (e.g. that maximizes the sum of player utilities) is NPC. The original NPC proof was by Gilboa and Zemel in the late 80s, and for a recent reference see, e.g., <http://www.cs.duke.edu/~conitzer/nashGEB08.pdf>


---

### Answer by username_3 on 2012-04-09. Score: 6

Shortest Vector in Lattice Problem, which is NP hard. The Gap version GapSVP is intermediate:

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


---

### Answer by username_4 on 2012-04-08. Score: 4

The equivalence of two finite closure systems (Moore families) $\mathbb{K}$ and $J$ on a finite set $M$. Where $\mathbb{K} = \{A\_i \subseteq M \}$ is given by the set of subsets of $M$ and a set $X$ is closed iff it can be obtained by an intersection of some sets from $\mathbb{K}$. The closure system $J = \{A\_i \rightarrow B\_i\}$ is given by the set of implications and a set $X$ is closed iff it respects all implications from $J$ i.e. for any $A\_i\rightarrow B\_i \in J$ if $A\_i \subseteq X$ then $B\_i \subseteq X$. The complexity of this problem is open and it is known that this problem is at least hard as dualization of monotone boolean functions.

But if we consider the problem: decide if the closure system of $J$ is a subset of closure system of $\mathbb{K}$ then not hard to proof that this problem becomes co-NP-complete.


---

