13
$\begingroup$

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. 
$\endgroup$
  • 5
    $\begingroup$ what do you mean by generation problem ? $\endgroup$ – Shiva Kintali Apr 5 '12 at 19:20
  • $\begingroup$ Sorry, I meant generalization. $\endgroup$ – sma Apr 5 '12 at 22:27
18
$\begingroup$

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

Generalizations are natural.

$\endgroup$
  • 10
    $\begingroup$ In particular, one generalization of GI is subgraph isomorphism, which is NPC $\endgroup$ – Suresh Venkat Apr 6 '12 at 5:55
14
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.