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.