4 ms·

It is funny that the author chose the SUBSET-SUM problem. You may be amazed but this is a special-case of the KNAPSACK problem for which we have: Fully polynom

by jlouis 16y ago

It is funny that the author chose the SUBSET-SUM problem. You may be amazed but this is a special-case of the KNAPSACK problem for which we have: Fully polynomial approximation schemes. Pseudo-polynomial time algorithms. In other words, you may find that for all practical purposes this problem can be solved so fast that it doesn't really warrant the NP-badge in some sense. You can say that the problem is an NP problem which disguises itself as a P problem. It would be really fun to use David Pisingers knapsack algorithm codes, http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html and then bait the bidder into finding a set for which the algorithm is NOT fast (hint: That is also pretty hard :)

pbhjpbhj 16y ago
>You can say that the problem is an NP problem which disguises itself as a P problem. It would be really fun to use David Pisingers knapsack algorithm codes, http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html and then bait the bidder into finding a set for which the algorithm is NOT fast (hint: That is also pretty hard :) This makes me think that the post could be a phish for programmers with strong maths comp-sci backgrounds, something Googlish? Please someone try this!
- jlouis 16y ago
  That would be fun, but alas, I don't have time. One can simply submit Pisingers "decomp" codes from the page I linked above, but if you do that, you are not the author of the work...
eru 16y ago
Yes. There's even a conjecture that says that for basically all NP problems all reasonable [1] instances will be solvable in expected polynomial time. Even if P != NP. [1] Add some hand-waving about probability distributions here.
- voidpointer 16y ago
  Does that include factoring large prime numbers? If a good approximation would exist for that, wouldn't that make public-key encryption pretty useless?
  - amalcon 16y ago
    Public-key encryption schemes would simply need to avoid reasonable circumstances. I suspect "product of two large primes" falls outside the "reasonable circumstances" for factoring.
    - eru 16y ago
      It's even harder than that. There are lots of known attacks, if you are not careful with your choice of prime numbers. (`Careful' is equal to `choosing pathological instances'.)
  - jerf 16y ago
    Included in that handwave about probability distributions was a caveat about not being handed pathological instances of problems. Encryption harnesses pathological instances and wouldn't be covered by such a handwave. (Is there ever any other reason to generate multi-hundred digit numbers and try to factor them? Honest question, if anybody's got a fun answer, though I am asking about something actually useful that you know about, not something hypothetical.)
    - eru 16y ago
      Actually, it's quite hard to come up with good primes for RSA. They need to avoid lots of properties, because researches have found efficient attacks on numbers with those properties.
  - eru 16y ago
    Factoring numbers is already suspected to be much easier than NP-complete. That is because factoring prime numbers is in the intersection between NP and co-NP. Co-NP is the set of problems where a "NO" answer is easily checkable with a certificate. If NP ?= co-NP is as much a question as P ?= NP. (I.e. no known proof either way, but every expects them to be unequal.)
antics 16y ago
I have a question, as a CS student. Why is finding a set for which the algorithm does not work (edit:) WELL so hard? I have admittedly not read anything about -- or indeed, heard of -- KNAPSACK, but my impression was that we could estimate running time based on various measures of complexity of the problem. Is this incorrect, or is measuring the complexity of NP problems simply incredibly difficult?
- jlouis 16y ago
  For all NP-problems, there are trivial instances. As an example the given instance might have structure which effectively makes it a P-problem. What makes NP-problems interesting is that there are also hard instances where the search breaks down and you end up walking an enormous solution space. Most NP-solvers "cheat" by looking at the structure of an instance in order to cut down the amount of searching it needs. How good they are depends on how good they are at cutting down the solution space. A lot of research is going into this - which is really a bet on P not equal to NP. The KNAPSACK problem is one of the "weak" NP problems in the sense that there is a pseudo-polynomial solution, see http://en.wikipedia.org/wiki/Pseudo-polynomial_time http://en.wikipedia.org/wiki/Pseudo-polynomial_time Intuitively, this means that KNAPSACK is still hard, but is easier than most other NP problems. Pisingers codes are so good that for most inputs the algorithm actually terminates quickly. There are still hard instances out there, but there are far between them. This means that a search for a hard instance might actually become rather cumbersome. Further, all realistic instances are probably realistically solvable so the instances we lack are more or less of theoretic interest. So when you call NP-problems hard it is because it has been proven there are some nasty instances among them for which even the most clever NP-solver algorithm for the problem gives up and resorts to basically searching the whole solution space in exponential time.
  - antics 16y ago
    But WHY are they trivial? Because we can extract metadata that help us prune the solution pool? And if that's the case for the KNAPSACK problem, does this hold for all such problems?

by jlouis 16y ago

pbhjpbhj 16y ago

>You can say that the problem is an NP problem which disguises itself as a P problem. It would be really fun to use David Pisingers knapsack algorithm codes, http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html http://www.diku.dk/hjemmesider/ansatte/pisinger/codes.html and then bait the bidder into finding a set for which the algorithm is NOT fast (hint: That is also pretty hard :) This makes me think that the post could be a phish for programmers with strong maths comp-sci backgrounds, something Googlish? Please someone try this!

jlouis 16y ago
That would be fun, but alas, I don't have time. One can simply submit Pisingers "decomp" codes from the page I linked above, but if you do that, you are not the author of the work...

eru 16y ago

Yes. There's even a conjecture that says that for basically all NP problems all reasonable [1] instances will be solvable in expected polynomial time. Even if P != NP. [1] Add some hand-waving about probability distributions here.

voidpointer 16y ago
Does that include factoring large prime numbers? If a good approximation would exist for that, wouldn't that make public-key encryption pretty useless?
- amalcon 16y ago
  Public-key encryption schemes would simply need to avoid reasonable circumstances. I suspect "product of two large primes" falls outside the "reasonable circumstances" for factoring.
  - eru 16y ago
    It's even harder than that. There are lots of known attacks, if you are not careful with your choice of prime numbers. (`Careful' is equal to `choosing pathological instances'.)
- jerf 16y ago
  Included in that handwave about probability distributions was a caveat about not being handed pathological instances of problems. Encryption harnesses pathological instances and wouldn't be covered by such a handwave. (Is there ever any other reason to generate multi-hundred digit numbers and try to factor them? Honest question, if anybody's got a fun answer, though I am asking about something actually useful that you know about, not something hypothetical.)
  - eru 16y ago
    Actually, it's quite hard to come up with good primes for RSA. They need to avoid lots of properties, because researches have found efficient attacks on numbers with those properties.
- eru 16y ago
  Factoring numbers is already suspected to be much easier than NP-complete. That is because factoring prime numbers is in the intersection between NP and co-NP. Co-NP is the set of problems where a "NO" answer is easily checkable with a certificate. If NP ?= co-NP is as much a question as P ?= NP. (I.e. no known proof either way, but every expects them to be unequal.)

antics 16y ago

I have a question, as a CS student. Why is finding a set for which the algorithm does not work (edit:) WELL so hard? I have admittedly not read anything about -- or indeed, heard of -- KNAPSACK, but my impression was that we could estimate running time based on various measures of complexity of the problem. Is this incorrect, or is measuring the complexity of NP problems simply incredibly difficult?

jlouis 16y ago
For all NP-problems, there are trivial instances. As an example the given instance might have structure which effectively makes it a P-problem. What makes NP-problems interesting is that there are also hard instances where the search breaks down and you end up walking an enormous solution space. Most NP-solvers "cheat" by looking at the structure of an instance in order to cut down the amount of searching it needs. How good they are depends on how good they are at cutting down the solution space. A lot of research is going into this - which is really a bet on P not equal to NP. The KNAPSACK problem is one of the "weak" NP problems in the sense that there is a pseudo-polynomial solution, see http://en.wikipedia.org/wiki/Pseudo-polynomial_time http://en.wikipedia.org/wiki/Pseudo-polynomial_time Intuitively, this means that KNAPSACK is still hard, but is easier than most other NP problems. Pisingers codes are so good that for most inputs the algorithm actually terminates quickly. There are still hard instances out there, but there are far between them. This means that a search for a hard instance might actually become rather cumbersome. Further, all realistic instances are probably realistically solvable so the instances we lack are more or less of theoretic interest. So when you call NP-problems hard it is because it has been proven there are some nasty instances among them for which even the most clever NP-solver algorithm for the problem gives up and resorts to basically searching the whole solution space in exponential time.
- antics 16y ago
  But WHY are they trivial? Because we can extract metadata that help us prune the solution pool? And if that's the case for the KNAPSACK problem, does this hold for all such problems?