# Can on every instance P = NP? [closed]

I want to ask a question concerning some aspects of the P vs. NP problem.

There are some results that people use to support a preference / belief about the conjecture $$P \neq NP$$ (e.g. separation of P and NP over other computation models or fields, some relativized versions, the inability of many people to find polynomial algorithms for any NP-complete problem, etc.)

My question is (not sure how to phrase it exactly):

What if for every "instance" of an NP-complete problem (e.g. 3-SAT) there exists a polynomial algorithm but there is not one fixed polynomial algorithm that solves all instances?

For example there are polynomial-time algorithms for special cases of a (generally) np-complete problem, etc..

Are these not indications about a possible P=NP result?

Are there results that point towards this direction?

What will be the implications for P vs. NP if that hypothesis (or does not hold)? Would it mean that the current context of P vs. NP may need revision and re-framing to capture these alternatives?

Thanks

UPDATE:

Possible sketch of proof that P=NP

1. If the PH collapses, it collapses as a whole (due to "symmetry of construction" of each level). It seems awkward that at some level the hierarchy collapses while not at other levels since by construction no such foundamental difference exists.

2. Show that that at some level there can be collapse.

3. => P=NP

• It doesn't quite make sense to talk about polynomial-time algorithms for each instance, but it does make sense to talk about polynomial-time algorithms for each input length, but not necessarily a uniform algorithm that works for all input lengths. I believe this captures the spirit of your question, and typically goes by the name circuit complexity. If there are such polynomial-sized non-uniform circuits, then it almost follows that NP=coNP (technically: PH collapses to ZPP^{NP}). Although this is still a far cry from P=NP, it is not nearly as far as the original circuit hypothesis seemed. Feb 14, 2014 at 18:25
• SAT solvers do not point in this direction, as 1) if a SAT solver worked in polynomial-time, it would be the same algorithm for every instance, and 2) for essentially all current SAT solvers, though they often work well in practice, there are inputs for which we know that they provably take exponential time. Lookup "resolution lower bounds" and other results in proof complexity. Feb 14, 2014 at 18:27
• As far as I can tell, you might also have, for instance, some sequence of infinite increasing subsets of 3SAT, each of which may be decided in polynomial time and whose limit is 3SAT, yet 3SAT is still not in P. Or something cool like that.
– usul
Feb 14, 2014 at 18:42
• I down voted the question because this is a research level Q&A site (see tour and help center) but you don't seem to be familiar with basics of complexity theory. You should first read an introduction to complexity theory book like Arora and Barak's book, that would resolve most of your confusions. Feb 14, 2014 at 20:17
• You have basic confusions and misunderstandings, they are off-topic here and will get resolved if you read a good textbook on complexity theory. Your comments are irrelevant to the on-topicness of this question on cstheory, read the links in my privious comment, they explain what we mean by research level on this site. And keep in mind this is not a discussion forum. Feb 14, 2014 at 22:12