-5
$\begingroup$

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

Improve this question
$\endgroup$
35
  • 9
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Feb 14, 2014 at 18:25
  • 3
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Feb 14, 2014 at 18:27
  • 1
    $\begingroup$ 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. $\endgroup$
    – usul
    Feb 14, 2014 at 18:42
  • 3
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Feb 14, 2014 at 20:17
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Feb 14, 2014 at 22:12

1 Answer 1

Reset to default
0
$\begingroup$

@NikosM. you've alluded to circuits, and Joshua Grochow answered that quite well. You mention fractional Knapsack which is NOT NP-complete and ask about "special families of parameters" for which a problem is solvable. There are numerous examples of this; for example the class FPT is the class of problems for which the running time of an algorithm is polynomial in the input size and exponential in a different program parameter (which if held constant yields a P-time algorithm). In brief, there are numerous ways in which people are trying to approach the P vs NP issue, and it's not clear whether it's even feasible to enumerate all of them here.

Your best bet is to study some basic complexity theory as Kaveh points out. Once you do that, we'd be happy to answer more directed questions about specific things.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanx, although i dont think this answers the question to the point, i will accept it, since part of it stems from my lack of proper jargon formulating the question in the first place $\endgroup$
    – Nikos M.
    Feb 14, 2014 at 22:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.