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

81–90 of 101 posts

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

#81

Post by empath-nirvana »

ngruhn wrote: post #62
fooker wrote: post #52

Earlier quoted context omitted.

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

Sure, but in practice that’s not what people worry about, from what I have seen. At least when dealing with SMT problems, the SAT part is the easy part.

I think that's because _in practice_ people don't waste their time working on intractable problems if they just want to get something done. There's almost always some way to avoid the intractable problem and approach it a different way.

It's sort of like how "in practice" it didn't matter for thousands of years that nobody understood electricity. Any problem that came up that would have required that knowledge to solve just got dropped, because they didn't have the tools to solve it.

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

#82

Post by adgjlsfhk1 »

shenberg wrote: post #55
adalacelove wrote: post #28

Earlier quoted context omitted.

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.

It actually doesn't require more memory for intermediate results (see the Strassen reloaded paper). It's more just that it's a ton of work to implement well (even compared to a regular gemm which is already hard), and the benefits only start showing up at pretty large (~4000x4000) matrices.

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

#84

Post by mort96 »

aatd86 wrote: post #51
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.

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)

No, it's absolutely a proof.

Claim: There is no odd number in {2, 4, 6}.

Proof: 2 is not an odd number, 4 is not an odd number, 6 is not an odd number, there are no other elements in {2, 4, 6}. Therefore, there is no odd number in {2, 4, 6}.

If there was simply an absence of proof, we would be forced to conclude that we don't know whether there's an odd number in {2, 4, 6}. That's clearly not the case.

The claim "S is a set with no odd number" is equivalent to the claim "S is a set where all numbers are even", which is something I assume you agree that we can prove.

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

#85

Post by luc4 »

> The class of problems solvable in a finite amount of memory is just the class of regular languages. The “finite memory” is the finite state machine used to solve them.

I think they meant to say "constant memory" since every halting Turing Machine uses finite memory.

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

#86

Post by openasocket »

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…

Another interesting take: P != NP could be true, while changing MANY things in reality.

Basically all modern asymmetric cryptography in common use rely on the difficulty of either integer factoring or discrete logarithms (including discrete logarithms of elliptic curves). The problem is, none of those problems are proven to be NP-complete! Even if we proved P != NP, there could still be polynomial time algorithms for integer factoring and/or discrete logarithms.

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

#87

Post by abetusk »

I like to think about this in terms of "ensembles", or a distribution on the problem instances you're drawing from. NP-Hard talks about worst case in this set or distribution, even if the "average" or "normal" case is creating an instance that is "easy" to solve.

This is part of the problem of using technical terms in a lay context. "Hard" here talks about "worst case hard" or "provably hard" (via a reduction to 3-SAT). Whether a given instance of an NP-Complete problem that is drawn from an ensemble or distribution is "intractable" is a more subtle question.

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

#88

Post by tetha »

beefield wrote: post #60
hnben wrote: post #53

Earlier quoted context omitted.

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.

That's what's called a "non-constructive" proof in some circles. It /doesn't/ have a useful path forward, which makes it frustrating. There are some weird sandwiches of complexity classes - like, iirc, P-SPACE, EXP, NP-SPACE - which we know to have exactly 2 subsets plus the total subset, but which constellations? Dunno.

This is different from a constructive proof. "Here we have a problem, and all algorithms so far are in O(n^3). We can demonstrate the existence of a substructure in all instances of this problem which lowers the complexity to O(n^2.978)" would be a huge constructive proof in some fields. Such a breakthrough could lead to a large number of follow-up improvements.

A non-constructive breakthrough is like "Yup, this is a barrier. No clue why though, but it's hard."

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

#89

Post by nonameiguess »

beefield wrote: post #37
vsnf wrote: post #5

Despite having done my undergrad in CS, I never understood what NP-hard really meant. I mean yeah, polynomial time, boolean logic, general-case not specific-case, transformable into other NP problems, I get it, but like, I don't get it? Anyway, after reading this article I feel like I've gotten one small step closer to filling in this gap in my CS knowledge.

> Despite having done my undergrad in CS, I never understood what NP-hard really meant Not having done CS undergrad, I have never really understood even P/NP. The naive explanation of problems that are easy to solve and check vs problems that are difficult to solve but easy to check seems to leave something essential out. I mean, with the naive explanation you are I think you are left with either of two options: 1. A…

You may want to take a look at https://cs.stackexchange.com/questions/38357/is-it-really-po...

Something along the lines of this is what you would likely need to do. Take some problem that is NP-complete. Prove it has an exponential lower bound on time complexity. You've just proved P != NP. Proof of impossibility is sufficiently common in mathematics that one of the oldest and best-known proofs of anything, Euclid's proof of the irrationality of sqrt(2), is an example of such a proof (it is impossible to express sqrt(2) as the ratio of two integers).

The philosophical issue relates more to physical non-existence. If I claim leprechauns don't exist, likely few people will argue with me, but I can't actually examine the universe outside of my own past and future light cones, so I can't really know for sure there is no part of larger existence that contains leprechauns. Even events that violate accepted physics may become possible if we live in a false vacuum that collapses to a state with a different physics at some time in the future. Proving mathematical non-existence is an entirely different animal. Trivially, any universally quantified proposition "for all X, predicate(X)" is logically equivalent to "for no X, not predicate(X)," yet proofs of such propositions abound.

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

#90

Post by openasocket »

beefield wrote: post #37
vsnf wrote: post #5

Despite having done my undergrad in CS, I never understood what NP-hard really meant. I mean yeah, polynomial time, boolean logic, general-case not specific-case, transformable into other NP problems, I get it, but like, I don't get it? Anyway, after reading this article I feel like I've gotten one small step closer to filling in this gap in my CS knowledge.

> Despite having done my undergrad in CS, I never understood what NP-hard really meant Not having done CS undergrad, I have never really understood even P/NP. The naive explanation of problems that are easy to solve and check vs problems that are difficult to solve but easy to check seems to leave something essential out. I mean, with the naive explanation you are I think you are left with either of two options: 1. A…

> A philosophical issue of not being able to prove a negative, you really can't prove that there is not a way to solve a problem fast.

You can definitely prove negatives, and we do so all the time. There's the undecidability of the halting problem, for example: there is no algorithm that can be expressed in a Turing-complete language that can determine if a particular program will halt or not.

Another fun one is the unsolvability of the quintic. You know how there's a formula for solving a quadratic equation (https://en.wikipedia.org/wiki/Quadratic_formula)? Well, there's also one for order 3 polynomials (cubics) and order 4 polynomials (quartics). But order 5 (quntics)? There is no formula that can solve quintic equations using addition, subtraction, multiplication, division, exponents, and radicals (square roots, cube roots, etc) in the general case. The theorem actually goes even further by providing explicit examples: the equation x^5 + x^3 + 1 has a root, approximately equal to -0.83762, which cannot be expressed in terms of the operations I listed above. This is all the consequence of Galois theory.

Post reply on HN