# Must every NP-Complete Problem have a class of instances which is solvable in Poly time? [closed]

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?

• You mean a subset of problems where a naive backtracking solver will never need to branch out? Commented Oct 31, 2017 at 16:08
• Not only NP-complete, but even unsolvable (in general) problems under some restrictions are solvable in poly-time. Commented Oct 31, 2017 at 16:16
• 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)$. Commented Oct 31, 2017 at 16:20
• @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. Commented Oct 31, 2017 at 16:25
• 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. Commented Oct 31, 2017 at 16:37