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…
NP-hard does not mean hard (2017)
91–100 of 101 posts
Re: NP-hard does not mean hard (2017)
#92In 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…
Re: NP-hard does not mean hard (2017)
#93Earlier 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.
Re: NP-hard does not mean hard (2017)
#94Earlier 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 even wrote that he proved it himself at the end)
Re: NP-hard does not mean hard (2017)
#95Earlier 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.
Re: NP-hard does not mean hard (2017)
#96Earlier 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...
Re: NP-hard does not mean hard (2017)
#97Earlier 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'…
Re: NP-hard does not mean hard (2017)
#98Earlier 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.
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)
#99Despite 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 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)
#100Corollary: 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…