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.
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ what do you mean by generation problem ? $\endgroup$– Shiva KintaliCommented Apr 5, 2012 at 19:20
-
$\begingroup$ Sorry, I meant generalization. $\endgroup$– smaCommented Apr 5, 2012 at 22:27
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
Most famously: Graph Isomorphism, and Dominating Set on Tournaments.
Generalizations are natural.
-
10$\begingroup$ In particular, one generalization of GI is subgraph isomorphism, which is NPC $\endgroup$ Commented Apr 6, 2012 at 5:55
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
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
answered Apr 9, 2012 at 21:35
$\begingroup$
$\endgroup$
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.
