Live data from Hacker News

NP-hard does not mean hard (2017)

jeremykun.com

91–100 of 101 posts

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

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

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…

[dead]

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

#92

In my experience, solving the NP-hard problem isn't the part that is hard, it's reducing the problem space and/or solution space to make it into a P-problem (when n is sufficiently big enough to worry about it). For example, changing how you're storing the data in the first place, or talking to PM/PO's to learn if you really need an exact solution or if a very close approximation is ok. Sometimes, you're even trying…

Computing a competitive equilibrium is NP-hard in Fisher Markets. [0] The economy is not controlled by some grand central institution calculating competitive equilibria. We have independent humans with some institutional soft constraints optimistically buying and selling things. Even if we assume that there is no information asymmetry and all preferences are known, everyone has to run the algorithm themselves in thei…

In my experience, every NP-hard problem I've run into was due to trying to solve it naively or "up-front" and can be reduced into something not-so-by-the-book which usually involves storing the data in a different form, or reducing scope (i.e., ignoring impossible solutions/values). I've yet to see a real-world NP-hard problem that can't be solved this way; but would never be accepted scientifically because they don't solve it in the 'general case.'

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

#93
post #47

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…

So, NP-hard means that it's either NP-complete (the hardest NP can get), or even harder than that. Pretty intuitive to me.

Yeah, one way to always read it is that X-hard, for most Xs here, means at least as hard as X.

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

#94
post #84
post #51

Earlier quoted context omitted.

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 i…

I'm not talking about the first part of the comment but the latter parts regarding the general case.

(I even wrote that he proved it himself at the end)

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

#95
post #38
post #36

Earlier quoted context omitted.

Are you stretching "this specific strategy for parallelizing P that I came up with won't work" to "there's no way to parallelize P"?

It’s more like : you win a Turing award by finding a strategy to parallelize this problem as you’ll be able to use that approach to parallelize all problems in P, proving NC = P.

This applies both ways. You'll win a Turing award if you prove NC ≠ P, which is kind of what you said — at least, that the best way I see of reading your first and a few following messages.

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

#96
post #34
post #33

Earlier quoted context omitted.

Cerium is correct, we don't know if P is efficiently parallelizable. Is there a formal proof of what you're talking about that we can read?

Are you perhaps confusing P with P complete? https://www.researchgate.net/profile/Walter-Ruzzo/publicatio...

What am I looking for in this 300 page document? Proof by intimidation, eh?

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

#97

Earlier quoted context omitted.

Computing a competitive equilibrium is NP-hard in Fisher Markets. [0] The economy is not controlled by some grand central institution calculating competitive equilibria. We have independent humans with some institutional soft constraints optimistically buying and selling things. Even if we assume that there is no information asymmetry and all preferences are known, everyone has to run the algorithm themselves in thei…

In my experience, every NP-hard problem I've run into was due to trying to solve it naively or "up-front" and can be reduced into something not-so-by-the-book which usually involves storing the data in a different form, or reducing scope (i.e., ignoring impossible solutions/values). I've yet to see a real-world NP-hard problem that can't be solved this way; but would never be accepted scientifically because they don'…

I guess you never tried to find optimal join orders for you sql engine.

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

#98
post #97

Earlier quoted context omitted.

In my experience, every NP-hard problem I've run into was due to trying to solve it naively or "up-front" and can be reduced into something not-so-by-the-book which usually involves storing the data in a different form, or reducing scope (i.e., ignoring impossible solutions/values). I've yet to see a real-world NP-hard problem that can't be solved this way; but would never be accepted scientifically because they don'…

I guess you never tried to find optimal join orders for you sql engine.

I actually have :), it was a time travelling database for $work. In our case, we assumed that queries wouldn't change too much (applications running on them tend to query the same tables over and over again). Thus we just picked an order "at random" (though IIRC, there were some heuristics) for table-sets, otherwise we used the best performing one seen so far -- but it would randomly run another query with a different order to keep finding the best one.

We just didn't care about trying to solve it 'up-front' and were more interested in empirically choosing the best solution.

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

#99
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…

Problems in P are about deciding whether an input passes or not, where there exists a 'turing machine/algorithm/black box' that will tell you if an input does, or does not pass in a 'fast way'. A simple example is graph coloring. The box contains a graph, you pass in a color for each node, and the box checks if there are no adjacent nodes with the same color. Note that this box has an input (the coloring) but also a sort of parameter (the graph) you can create many different instances of this box by just changing the graph.

You could also add another parameter, call it K. This will be the maximum number of colors you can use. It is still easy for the box to check if a coloring fits this criteria.

For problems in NP, there is an underlying set of boxes in P. The input to an NP problem is a set of parameters that describe a box in P. In other words, any input for an NP problem corresponds to a 'fast box'. The NP problem then asks, "is there any input this fast box will accept". Such an accepted input is called a witness, because it proves that the box created by the input to the NP problem is solvable.

In the graph coloring example, instead of having a graph, a number of colors K, and a coloring to check, you now have: a graph and a number of colors, and the question 'can we find any coloring'.

We transformed a 'check a solution' into a 'find if a solution exists'. A key element here is that someone attempting the NP problem gets to look inside the box, figure out how it works.

In your example of 'you have to guess the number I thought of', you need to hand the guesser a box that will check that number. The guesser can then look inside the box to see how it works. So a simple comparison with a fixed value allows the guesser to 'read the hardcoded value from the source code'.

Do note that the box in P has to be fully deterministic.

In an NP problem, an input describes some parameters

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

#100
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…

[deleted]
Post reply on HN