Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

NP-hard does not mean hard (2017)

jeremykun.com

Post reply on HN
Print view View original

51–60 of 101 posts

Re: NP-hard does not mean hard (2017)

#51

Post by aatd86 »

beefield wrote: post #46
aatd86 wrote: post #42

Earlier quoted context omitted.

Wait, how is it impossible to prove a negative?

Well, I guess you can prove that there are no odd numbers in set (2,4,6), so some negatives you can prove, but in general case, I do not know how to prove that something does not exist and will not exist ever.

That's the absence of proof. It's a bit different from the proof of a negative.

Don't worry you're not the first one mentioning it so that's something that must be some kind of colloquialism somewhere but I was asking to understand what people may have meant.

To top it all, you proved a negative (by providing a counterexample) :o)

Re: NP-hard does not mean hard (2017)

#52

Post by fooker »

ngruhn wrote: post #50

Traveling salesmen is even solved to optimality (no heuristics) for pretty large instances with integer programming techniques. Also SAT is pretty much a solved problem. With algorithms like CDCL. This really surprised me. I also left my first complexity theory course believing that NP-hard = "not solvable in practice“

> SAT is pretty much a solved problem

We don’t really understand what makes some SAT problems harder than others.

You can go from a problem solvable with CDCL in a few seconds to one that would outlast the solar system by changing a couple of input bits.

Re: NP-hard does not mean hard (2017)

#53

Post by hnben »

beefield wrote: post #46
aatd86 wrote: post #42

Earlier quoted context omitted.

Wait, how is it impossible to prove a negative?

Well, I guess you can prove that there are no odd numbers in set (2,4,6), so some negatives you can prove, but in general case, I do not know how to prove that something does not exist and will not exist ever.

when proving a negativ in math, you often do a proof by contradiction

precondition: Either A is true or it is false.

question: is A false?

solution:

1. assume that A is true

2.

3. find a contradiction

4. ==> A can not be true

5. ==> therefor A is false

Re: NP-hard does not mean hard (2017)

#54

Post by Dylan16807 »

tetha wrote: post #23
lambda wrote: post #7

Corollary: P does not mean easy. Most things that you do on the computer, you want to be O(n) or less; maybe O(n log n) or even O(n log^x n), but no slower than that. That means if you get a bigger problem, you can generally just get a proportionally bigger computer and be all set. Now, sure, there are plenty of O(n^2) problems where the n stays small enough, or you don't mind waiting or spending a ton of money on it…

Our CS-Prof also had another interesting point: P = NP could be true without changing many things in reality. This could occur if the reduction of an NP-complete problem onto a polynomial problem results in a runtime of such monstrous polynomial degree that the exponential algorithms are just faster for every tractable problem size. Something like this exists in some graph algorithms - theoretically faster algorithms…

> This could occur if the reduction of an NP-complete problem onto a polynomial problem results in a runtime of such monstrous polynomial degree that the exponential algorithms are just faster for every tractable problem size.

You don't even need to go that far.

n^8 is smaller than 2^n once you get past 44, still well in the tractable range, but encrypting something against n^8 brute force is a pretty reasonable task.

Re: NP-hard does not mean hard (2017)

#55

Post by shenberg »

adalacelove wrote: post #28
tetha wrote: post #23

Earlier quoted context omitted.

Our CS-Prof also had another interesting point: P = NP could be true without changing many things in reality. This could occur if the reduction of an NP-complete problem onto a polynomial problem results in a runtime of such monstrous polynomial degree that the exponential algorithms are just faster for every tractable problem size. Something like this exists in some graph algorithms - theoretically faster algorithms…

Staying in the realm of polynomial complexity matrix multiplication comes to mind, where we are approaching more and more O(n^2), where O(n^3) is the naive, but more common implementation.

In terms of practical algorithms, the Strassen algorithm (O(n^2.8)) is the only one that has runtime advantages for matrix sizes that aren't enormous, and even then, it's not always used because it has two non-trivial costs: reduced numerical stability and more memory space requirements for intermediate results.

Re: NP-hard does not mean hard (2017)

#56

Post by [deleted] »

tgv wrote: post #41
dandanua wrote: post #32

Earlier quoted context omitted.

It's probably due to unfortunate naming of things. First, NP doesn't mean "non polynomial", though people can imply that since there are no known polynomial solvers for NP-complete problems. It's a shorthand for "nondeterministic polynomial", but that naming is not intuitive either. It's a class of problems that has polynomial verifiers of solutions. Second, NP-hard means the problem is either NP-complete or not in N…

> Second, NP-hard means the problem is either NP-complete or not in NP at all. Which is another confusing naming, because problems not in NP are NP-hard. But remember that P is in NP, so NP-hard implies not in P (assuming P ≠ NP).

[deleted]

Re: NP-hard does not mean hard (2017)

#57

Post by chriswarbo »

dwattttt wrote: post #13
lambda wrote: post #7

Corollary: P does not mean easy. Most things that you do on the computer, you want to be O(n) or less; maybe O(n log n) or even O(n log^x n), but no slower than that. That means if you get a bigger problem, you can generally just get a proportionally bigger computer and be all set. Now, sure, there are plenty of O(n^2) problems where the n stays small enough, or you don't mind waiting or spending a ton of money on it…

A terrific teardown of tracking down an unexpected O(n^2): https://randomascii.wordpress.com/2021/02/16/arranging-invis...

The "accidentally quadratic" blog collected such things. Not sure if it's still being updated since Tumblr's mass exodus (the posts don't seem to show timestamps) https://accidentallyquadratic.tumblr.com

Re: NP-hard does not mean hard (2017)

#58

Post by dandanua »

tgv wrote: post #41
dandanua wrote: post #32

Earlier quoted context omitted.

It's probably due to unfortunate naming of things. First, NP doesn't mean "non polynomial", though people can imply that since there are no known polynomial solvers for NP-complete problems. It's a shorthand for "nondeterministic polynomial", but that naming is not intuitive either. It's a class of problems that has polynomial verifiers of solutions. Second, NP-hard means the problem is either NP-complete or not in N…

> Second, NP-hard means the problem is either NP-complete or not in NP at all. Which is another confusing naming, because problems not in NP are NP-hard. But remember that P is in NP, so NP-hard implies not in P (assuming P ≠ NP).

And if P = NP any problem will be NP-hard. Until P ≠ NP is proved we can't heavily rely on the consequences.

Re: NP-hard does not mean hard (2017)

#59

Post by nabla9 »

lambda wrote: post #7

Corollary: P does not mean easy. Most things that you do on the computer, you want to be O(n) or less; maybe O(n log n) or even O(n log^x n), but no slower than that. That means if you get a bigger problem, you can generally just get a proportionally bigger computer and be all set. Now, sure, there are plenty of O(n^2) problems where the n stays small enough, or you don't mind waiting or spending a ton of money on it…

Matrix multiplication is O(n^2.73) time and O(n^2) space. That's what eats bigger and bigger chunk of electricity nowadays.

Re: NP-hard does not mean hard (2017)

#60

Post by beefield »

hnben wrote: post #53
beefield wrote: post #46

Earlier quoted context omitted.

Well, I guess you can prove that there are no odd numbers in set (2,4,6), so some negatives you can prove, but in general case, I do not know how to prove that something does not exist and will not exist ever.

when proving a negativ in math, you often do a proof by contradiction precondition: Either A is true or it is false. question: is A false? solution: 1. assume that A is true 2. 3. find a contradiction 4. ==> A can not be true 5. ==> therefor A is false

In P/NP case I would need to assume that I can solve a problem in polynomial time, and then find a contradiction. To me it is really hard to see a useful path forward from there.
Post reply on HN