Timeline for Complexity :: Integer Programming :: Non-Poly Example [closed]
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 27, 2015 at 21:10 | history | closed |
Dima Pasechnik Dirk Alex Degtyarev Ryan Budney Stefan Kohl♦ |
Needs details or clarity | |
| Apr 27, 2015 at 20:41 | comment | added | Hugh | the failing is clearly my own.. my assumption was that i would get an answer along the lines of: 01 problem X(array of length n=4) can be solved in O(n), but if you increase n beyond such a threshold any attempts to solve such a problem show a complexity of 2**(O(n)) or whatever, and even if you were to find an algo that could solve the array of abitrary length in under 2**(O(log(n))) you would still need to devise an algo to do the same for a problem with a graph of n vertices, etc. before you could say all 01 problems are poly .. how could i ask the question to receive such an answer? | |
| Apr 27, 2015 at 19:44 | comment | added | Dima Pasechnik | an example in this area is something that depends on a parameter; say, an array of length $n$ of integer numbers, and the task is to sort them; or a graph on $n$ vertices, and the task is to find a maximum clique. See, it's crucial that there is $n$ involved, because the question computational complexity answers is "provide a function of $n$ that tells the number of operations needed to solve the task". | |
| Apr 27, 2015 at 19:08 | history | edited | Hugh | CC BY-SA 3.0 |
added 81 characters in body
|
| Apr 27, 2015 at 19:07 | comment | added | Hugh | 'there is no individual instance of a problem for which a solution would contradict P not equal to NP', i am unsure what question you think you are answering by saying this? i am well aware that the algo is what would contradict P=/=NP.. i asked for potential counter examples, where one could potentially find such an algorithm, i suppose people are getting hung up on the phrasing of 'would' and 'one of these'? i will edit it to be more general in its language | |
| Apr 27, 2015 at 18:48 | comment | added | Hugh | my question agrees with your sentiment as per scaling: 'Complexity theory is about how the performance of algorithms scales as input size grows' .. 'follow up a quick runtime example with the same example now with the added necessary complexity to cause it to be NP-hard' | |
| Apr 27, 2015 at 18:38 | comment | added | Sasho Nikolov | No, there is no individual instance of a problem for which a solution would contradict P not equal to NP. Complexity theory is about how the performance of algorithms scales as input size grows. A fixed input doesn't show anything about scaling. That said, random k-SAT instances near the satisfiability threshold appear to be very hard, so they provide a good benchmark (see this blog post and links in it windowsontheory.org/2013/10/07/…). You can easily turn them into 0-1 IPs using the standard hardness reduction. | |
| Apr 27, 2015 at 18:24 | history | edited | Hugh | CC BY-SA 3.0 |
proven was the wrong word
|
| Apr 27, 2015 at 17:59 | comment | added | Hugh | i suppose i have trouble seeing how you can have one without the other.. i think you are understanding my question in reverse though: stead asking for an example that shows a problem is in fact NP-Complete ie. individual defines a class, i am asking for examples for potential counter examples which in fact can be individual; openculture.com/2015/04/… | |
| Apr 27, 2015 at 17:11 | review | Close votes | |||
| Apr 27, 2015 at 21:10 | |||||
| Apr 27, 2015 at 16:52 | comment | added | Dima Pasechnik | the notions of NP-completeness and polynomial-time solvability are about classes of problems, and not individual examples. | |
| Apr 27, 2015 at 15:06 | review | First posts | |||
| Apr 27, 2015 at 15:08 | |||||
| Apr 27, 2015 at 15:02 | history | asked | Hugh | CC BY-SA 3.0 |