Is there any theorem that states that any NP-Complete Problem has a class of instances solvable in Poly time? For example, some problems like vertex cover are NP-Complete on general graphs but can be solved in polynomial time on instances which are Trees. Does every NP-Complete problem have such class?

  • $\begingroup$ You mean a subset of problems where a naive backtracking solver will never need to branch out? $\endgroup$ Commented Oct 31, 2017 at 16:08
  • $\begingroup$ Not only NP-complete, but even unsolvable (in general) problems under some restrictions are solvable in poly-time. $\endgroup$
    – rus9384
    Commented Oct 31, 2017 at 16:16
  • 3
    $\begingroup$ Will this work: If the class of instances is finite then they are solvable in $O(1)$. For example if you create a class of any 10 instances of the Vertex cover then they are solvable in $O(1)$. $\endgroup$
    – fade2black
    Commented Oct 31, 2017 at 16:20
  • 1
    $\begingroup$ @fade2black, yeah, surely there should be instances that can be solved in $O(1)$ time also. Like SAT where first $O(1)$ clauses form unsatisfiable formula. There are infinitely many of them. $\endgroup$
    – rus9384
    Commented Oct 31, 2017 at 16:25
  • $\begingroup$ Also, every NP-complete problem is reducible to 3SAT. If you manage to create a 1-1 reduction from problem instances to a 3SAT then all "special" instances reducible to 2SAT are solvable in polytime. $\endgroup$
    – fade2black
    Commented Oct 31, 2017 at 16:37


Browse other questions tagged or ask your own question.