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

<p>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. </p>

CC BY-SA 3.0
2014-02-14T22:26:29.907Z
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.
CC BY-SA 3.0
2014-02-14T22:20:11.250Z
2014-02-14T22:20:11.250Z
Suresh Venkat
<p>I want to ask a question concerning some aspects of the P vs. NP problem.</p>
<p>There are some results that people use to support a preference / belief about the conjecture <span class="math-container">$P \neq NP$</span> (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.)</p>
<p>My question is (not sure how to phrase it exactly):</p>
<blockquote>
<p>What if for every &quot;instance&quot; of an NP-complete problem (e.g. 3-SAT) there exists a polynomial algorithm but there is not <em>one</em> fixed polynomial algorithm that solves all instances?</p>
</blockquote>
<p>For example there are polynomial-time algorithms for special cases of a (generally) np-complete problem, etc..</p>
<p>Are these not indications about a possible P=NP result?</p>
<p>Are there results that point towards this direction?</p>
<p>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?</p>
<p>Thanks</p>
<p>UPDATE:</p>
<p><strong>Possible sketch of proof that P=NP</strong></p>
<ol>
<li><p>If the PH collapses, it collapses as a whole (due to &quot;symmetry of construction&quot; 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.</p>
</li>
<li><p>Show that that at some level there can be collapse.</p>
</li>
<li><p>=&gt; P=NP</p>
</li>
</ol>

CC BY-SA 3.0
2014-02-14T18:25:57.680Z
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
CC BY-SA 3.0
2014-02-14T18:27:25.283Z
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
CC BY-SA 3.0
2014-02-14T18:30:31.637Z
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.
CC BY-SA 3.0
2014-02-14T18:33:28.870Z
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.
CC BY-SA 3.0
2014-02-14T18:41:55.880Z
@joshua, can you point me to any references about circuit complexity in this context, much appreciated
Nikos M.
CC BY-SA 3.0
2014-02-14T18:42:10.393Z
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
CC BY-SA 3.0
2014-02-14T18:45:22.063Z
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
CC BY-SA 3.0
2014-02-14T18:49:30.870Z
@JoshuaGrochow, can you point me to any references about circuit complexity in this context, much appreciated
Nikos M.
CC BY-SA 3.0
2014-02-14T19:11:55.513Z
@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.
CC BY-SA 3.0
2014-02-14T19:38:41.553Z
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.
CC BY-SA 3.0
2014-02-14T20:17:24.547Z
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
CC BY-SA 3.0
2014-02-14T21:15:07.940Z
@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.
CC BY-SA 3.0
2014-02-14T21:18:45.710Z
@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.
CC BY-SA 3.0
2014-02-14T21:37:09.567Z
@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.
CC BY-SA 3.0
2014-02-14T21:43:28.050Z
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
CC BY-SA 3.0
2014-02-14T21:45:48.110Z
@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.
CC BY-SA 3.0
2014-02-14T21:54:56.567Z
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
CC BY-SA 3.0
2014-02-14T21:57:06.853Z
@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.
CC BY-SA 3.0
2014-02-14T22:03:59.263Z
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.
CC BY-SA 3.0
2014-02-14T22:04:20.813Z
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
CC BY-SA 3.0
2014-02-14T22:07:12.403Z
@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.
CC BY-SA 3.0
2014-02-14T22:12:58.267Z
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
CC BY-SA 3.0
2014-02-14T22:15:14.083Z
@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.
CC BY-SA 3.0
2014-02-14T22:21:11.550Z
@DavidRicherby, post edited to reflect the point better
Nikos M.
CC BY-SA 3.0
2014-02-14T22:21:58.087Z
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
CC BY-SA 3.0
2014-02-14T22:31:55.593Z
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
CC BY-SA 3.0
2014-02-14T22:35:30.937Z
@Kaveh thanx, see also the comment on the accepted answer
Nikos M.
CC BY-SA 3.0
2014-02-14T22:54:24.577Z
@JoshuaGrochow, thanx, your comments were really valuable and indeed gave insight and hints
Nikos M.
CC BY-SA 3.0
2014-02-14T23:03:59.897Z
@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
CC BY-SA 3.0
2014-02-14T23:15:24.447Z
@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.
CC BY-SA 3.0
2014-02-14T23:18:55.030Z
@NikosM. , I think for some reason nobody has mentioned this yet, but please do use [cs.stackexchange.com](http://cs.stackexchange.com) for questions along these lines (though usually the more specific the better). They are just not as on-topic here.
usul
CC BY-SA 3.0
2014-02-14T23:23:01.890Z
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
CC BY-SA 3.0
2014-02-14T23:40:49.590Z
@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.
CC BY-SA 3.0
2014-02-15T15:28:36.370Z
edited the question with additional thoughts about the issue and a little more "crankiness", thanks anyway
Nikos M.
CC BY-SA 3.0
2014-02-15T15:47:19.940Z
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.
<cc.complexity-theory><p-vs-np>
Can on every instance P = NP?
Nikos M.
# Can on every instance P = NP?

(Asked by: username_0 on 2014-02-14)

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

**Tags:** cc.complexity-theory, p-vs-np

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: 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  
> **username_0**: 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  
> **username_0**: @joshua, can you point me to any references about circuit complexity in this context, much appreciated  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_0**: @JoshuaGrochow, can you point me to any references about circuit complexity in this context, much appreciated  
> **username_0**: @username_2, is this sth like saying that P=NP "almost everywhere", bare with me on these "metaphors", but i think the meaning is clear  
> **username_0**: why the downvote? the question does not show research effort, unclear or not useful? i guess someone can point me to such information? appreciated  
> **username_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.  
> **username_0**: @username_3, 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  
> **username_0**: @username_3, 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)?  
> **username_0**: @username_3, 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  
> **username_4**: 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.  
> **username_0**: @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)?  
> **username_4**: 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.  
> **username_0**: @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  
> **username_0**: 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?  
> **username_5**: 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?  
> **username_0**: @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)  
> **username_3**: 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.  
> **username_0**: @username_3, 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)?  
> **username_0**: @DavidRicherby, post edited to reflect the point better  
> **username_3**: 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.  
> **username_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?  
> **username_0**: @username_3 thanx, see also the comment on the accepted answer  
> **username_0**: @JoshuaGrochow, thanx, your comments were really valuable and indeed gave insight and hints  
> **username_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!  
> **username_0**: @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  
> **username_2**: @NikosM. , I think for some reason nobody has mentioned this yet, but please do use [cs.stackexchange.com](http://cs.stackexchange.com) for questions along these lines (though usually the more specific the better). They are just not as on-topic here.  
> **username_3**: 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.  
> **username_0**: @username_3, yes please i will roll back, since some things were deleted, i can leave the other edits, how do i roll back?  
> **username_0**: edited the question with additional thoughts about the issue and a little more "crankiness", thanks anyway  
> **username_0**: 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  

---

## 1 answers

### Answer by username_6 on 2014-02-14. Score: 0 | Accepted answer

@NikosM. you've alluded to circuits, and username_1 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 username_3 points out. Once you do that, we'd be happy to answer more directed questions about specific things.

> **Comments:**
> **username_0**: 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  

---

