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?


closed as unclear what you're asking by David Richerby, fade2black, Evil, Yuval Filmus, quicksort Nov 19 '17 at 22:34

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ You mean a subset of problems where a naive backtracking solver will never need to branch out? $\endgroup$ – ratchet freak Oct 31 '17 at 16:08
  • $\begingroup$ Not only NP-complete, but even unsolvable (in general) problems under some restrictions are solvable in poly-time. $\endgroup$ – rus9384 Oct 31 '17 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 Oct 31 '17 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 Oct 31 '17 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 Oct 31 '17 at 16:37