-5

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

Nikos M.
  • 581
  • 2
  • 9
  • 9
    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. – Joshua Grochow Feb 14 '14 at 18:25
  • 3
    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. – Joshua Grochow Feb 14 '14 at 18:27
  • Thanks for the comment, the first comment captures much of the question truly, sat solvers was probably a bad example, how about algorithms that are fine-tuned accordng to a specific instance, this is closer – Nikos M. Feb 14 '14 at 18:30
  • i must state that i am not quite versatile in the complexity zoo, however i think that the relativization barrier may also point at this direction, for some "oracles" P=NP, seems like "fine-tuning" to me – Nikos M. Feb 14 '14 at 18:33
  • @joshua, can you point me to any references about circuit complexity in this context, much appreciated – Nikos M. Feb 14 '14 at 18:41
  • 1
    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 '14 at 18:42
  • 1
    I guess there are trivial examples of the above, along the lines of http://cstheory.stackexchange.com/questions/20819/can-limit-of-hard-languages-be-easy . So this intuition might be difficult to formalize. – usul Feb 14 '14 at 18:45
  • @JoshuaGrochow, can you point me to any references about circuit complexity in this context, much appreciated – Nikos M. Feb 14 '14 at 18:49
  • @usul, is this sth like saying that P=NP "almost everywhere", bare with me on these "metaphors", but i think the meaning is clear – Nikos M. Feb 14 '14 at 19:11
  • why the downvote? the question does not show research effort, unclear or not useful? i guess someone can point me to such information? appreciated – Nikos M. Feb 14 '14 at 19:38
  • 3
    I down voted the question because this is a research level Q&A site (see [about] and [help/on-topic]) 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. – Kaveh Feb 14 '14 at 20:17
  • 1
    @Kaveh, its ok you are free to vote whichever you want, i am not a computer theory professor or researcher but a mere engineer. i was not aware this is research-only forum, anyway i already know the basics of complexity theory although not fully versatile in all the complexity species outthere (BQP, etc..), however havent found anything addressing this issue, so if you have sth you can point me to for this issue (does not matter the level it requires), it is appreciated – Nikos M. Feb 14 '14 at 21:15
  • 1
    @Kaveh, by the way why isnt this a "research question", is it ridiculus, resolved, vague? all of the above? none of the above? i can understand vagueness i have hard time formulating the question myself, but isnt this what research is about (or part of)? – Nikos M. Feb 14 '14 at 21:18
  • 1
    @Kaveh, if you will, a hint of the question is that maybe the P / NP problem is ill-posed as is right now, and an example is given by giving posibilities of polynomial algorithms not formalized by the current context, other examples involve quantum computing or in general the computing model and how physically realizable it is – Nikos M. Feb 14 '14 at 21:37
  • this is not well posed because polynomial time does not make sense unless you have an infinite family of instances. also, there is a very simple "algorithm" that works for a single instance: hardwire the instance and answer into the algorithm, check that you got the correct instance, output correct answer. – Sasho Nikolov Feb 14 '14 at 21:43
  • @SashoNikolov, the answer makes sense, is there any alternative? see also previous comment, how about having many sets/families of instances (infinite in themselves) that still require different "fine-tuning" (for lack of better word)? – Nikos M. Feb 14 '14 at 21:45
  • i am not sure what you mean by fine tuning. or what the question is. many problems have natural easy subcases, e.g. maximum independent set for perfect graphs. – Sasho Nikolov Feb 14 '14 at 21:54
  • @SashoNikolov, i was thinking of algorithms like the fractional knapshack, this definately solves an np-complete problem (when it uses fractional numbers), sth like along these lines – Nikos M. Feb 14 '14 at 21:57
  • 1
    let me elaborate on this for a sec, considering the knapshack problem (in general np-complete) depending on the parameters of the problem there are polynomial solutions (like fractional knapshack), how about other "special" polynomial solutions for other families of parameters for the same np-complete problem? As it stands i dont see (except if you know sth to point me to) any attempted solutions along these lines? – Nikos M. Feb 14 '14 at 22:03
  • You lost me at the point where you accused mainstream computer scientists of being elitist. Seriously, how much time do you expect me to spend interacting with a complete stranger who starts off by insulting me? – David Richerby Feb 14 '14 at 22:04
  • 1
    @DavidRicherby, you are right, and it is not your fault, but you must admit that there is a lot of such "crazy-making" going on around this issue, so i just took a stand there (just google around) – Nikos M. Feb 14 '14 at 22:07
  • 2
    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. – Kaveh Feb 14 '14 at 22:12
  • 1
    @Kaveh, ok point taken, sorry for your time, can you point me to another forum i can pose this question (and expect to get an answer for it)? – Nikos M. Feb 14 '14 at 22:15
  • @DavidRicherby, post edited to reflect the point better – Nikos M. Feb 14 '14 at 22:21
  • P vs. NP is a mathematical statement, and every expert in complexity theory knows that it is a nice easy to state abstraction and simplification of the real world and it doesn't correspond completely to practice. E.g. no one considers an algorithm with $n^{100000}$ or $2^{10000}n$ running time as feasible in practice, and there are many other similar issues. Go read a good textbook, it will resolve your confusions. – Kaveh Feb 14 '14 at 22:21
  • 1
    The textbook by Arora & Barak surely has the results I stated in it. The result I was alluding to is a slight strengthening of the well-known Karp-Lipton Theorem. Whatever else you might mean by "each instance can be solved in polynomial time" (and I can imagine several different definitions that would formalize in a meaningful what I think you're trying to get), I'm pretty sure that circuit complexity is a more lenient and general possibility. I do, however, agree that this isn't really the right forum for this level of question - maybe cs.stackexchange instead? – Joshua Grochow Feb 14 '14 at 22:31
  • @Kaveh thanx, see also the comment on the accepted answer – Nikos M. Feb 14 '14 at 22:35
  • @JoshuaGrochow, thanx, your comments were really valuable and indeed gave insight and hints – Nikos M. Feb 14 '14 at 22:54
  • 1
    @NikosM.: You're welcome. I normally don't engage those I judge to be cranks, but based on this single exchange I wouldn't put you in that category. You seem to me more like a well-intentioned and interested engineer, who simply hasn't learned a ton of complexity theory yet and is asking (vague/big-picture/...) questions that I think it would be natural for someone learning complexity to ask. (But this particular forum is not aimed at such an audience.) You might also find this interesting: http://cstheory.stackexchange.com/q/17676/129. Best of luck! – Joshua Grochow Feb 14 '14 at 23:03
  • @JoshuaGrochow, although i dont want to waste anyones time, by avoiding the "crank" label and engaging (even for a sec) you actually provided valuable suggestions, maybe this can be sth for all of us to take – Nikos M. Feb 14 '14 at 23:15
  • @NikosM. , I think for some reason nobody has mentioned this yet, but please do use cs.stackexchange.com for questions along these lines (though usually the more specific the better). They are just not as on-topic here. – usul Feb 14 '14 at 23:18
  • I edited the question a bit to make it easier to read and put it in a shape that can be migrated to [cs.se]. Feel free to roll back my edits or edit further if you feel they changed what you wanted to ask. – Kaveh Feb 14 '14 at 23:23
  • 1
    @Kaveh, yes please i will roll back, since some things were deleted, i can leave the other edits, how do i roll back? – Nikos M. Feb 14 '14 at 23:40
  • 1
    edited the question with additional thoughts about the issue and a little more "crankiness", thanks anyway – Nikos M. Feb 15 '14 at 15:28
  • 1
    the question highlights 2 issues 1. a possible explanation of why no algorithm found for an abstract np-complete problem (many algorithms per sets of instances) 2. an equivalent (if not stronger) intuition about why P=NP is plausible despite "popular" "crazy-making" around such issues, point clear thanks – Nikos M. Feb 15 '14 at 15:47

1 Answers1

0

@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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • 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 – Nikos M. Feb 14 '14 at 22:26