1
$\begingroup$

When learning about computational complexity I find that when discussing the NP-Complete problems authors always give examples of such problems that can in fact be solved in poly time.

I understand this as a teaching aide but to fail to follow up a quick runtime example with the same example now with the added necessary complexity to cause it to be NP-hard seems an unfortunate omission.

What I was wondering was if someone could show me an example of an 0-1 integer programming problem that if solved in polynomial time would grab a unicorn by the horn after having its logic's generality proved.

for example.. and i know integer factorization has yet to find its place in the complexity spectrum but talking about the difficulty of integer factorization and then explaining the process as finding that 21=3x7 does little to show someone trying to understand the algorithms for the problem, whereas showing an individual the RSA challenge problems makes clear the difficulties in the problem and grants an 'if an algo solves all of these and subsequently any factoring effort in poly then the complexity of factorization is definitely in P'

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ the notions of NP-completeness and polynomial-time solvability are about classes of problems, and not individual examples. $\endgroup$
    – Dima Pasechnik
    Commented Apr 27, 2015 at 16:52
  • $\begingroup$ 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/… $\endgroup$
    – Hugh
    Commented Apr 27, 2015 at 17:59
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Apr 27, 2015 at 18:38
  • $\begingroup$ 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' $\endgroup$
    – Hugh
    Commented Apr 27, 2015 at 18:48
  • 1
    $\begingroup$ 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". $\endgroup$
    – Dima Pasechnik
    Commented Apr 27, 2015 at 19:44

0

Reset to default

Browse other questions tagged .