12 ms·

NP-hard does not mean hard (2017)

128 points by stefanpie 3y ago

mutant_glofish 3y ago
Hey, I vouched for your submission. Just wanted to let you know that there seems to be some issue with your account causing your submissions to be automatically flagged. You may want to contact HN moderators (hn@ycombinator.com) about that.
- dang 3y ago
  I've fixed it now. Thanks for watching out for a fellow user!
deleted 3y ago
[deleted]
vsnf 3y ago
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.
- deleted 3y ago
  [deleted]
  - Ar-Curunir 3y ago
    For cryptography, every instance is (conjectured to be) complex, not just laborious. For worst-case NP-hardness, the complex instances are also laborious, while the simple instances are not laborious.
- jandrese 3y ago
  From what I remember: NP: Finding the solution takes more than polynomial time, but you can verify the answer is correct in polynomial time. NP-Hard: Finding the solution takes more than polynomial time, and it also takes more than polynomial time to verify that the solution is correct. NP-Complete: NP-Hard, but it can be transformed into any other NP-Complete problem in polynomial time. This is special because it means if you find a solution for any NP-Complete problem, you have found a solution for all of them. Finding an NP-Complete solution always seemed rather rather optimistic to me, but computer science professors obsessed over these problems. Caveat: It has been more than 20 years since I was quizzed on this stuff, so it might be wrong.
  - quickthrower2 3y ago
    --Edit: this was wrong, see reply comment-- NP: you can verify the answer is correct in polynomial time. (and no other clauses) Anything in P is in NP
    - Dylan16807 3y ago
      I think it's worth saying what NP stands for. Nondeterministic Polynomial. Where "nondeterministic" basically means you get to try every single polynomial solution in parallel.
    - minitech 3y ago
      Not wrong, just a different criterion that describes the same complexity class.
    - raincole 3y ago
      > --Edit: this was wrong, see reply comment-- You're not wrong tho. NP problems can be verified in polynomial time. Nondetermisitic turnig machine is like a turing machine that has multiple "next steps" instead of one at a given time, and can migically choose the correct next step. You can think it as "taking all the possible paths at the same time (but at the end only the correct one matters)". But you can also think it as "given all the 'choices' it made, check if there is actually such a path", in other words, verifying a certification.
- dandanua 3y ago
  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 NP at all. Which is another confusing naming, because problems not in NP are NP-hard. As a saying goes, there are two main problems in programming - naming things and cache invalidation. And in this case the former fails badly.
  - tgv 3y ago
    > 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 3y ago
      [deleted]
    - dandanua 3y ago
      And if P = NP any problem will be NP-hard. Until P ≠ NP is proved we can't heavily rely on the consequences.
      - tgv 3y ago
        That's an exaggeration. It's pretty safe to assume P ≠ NP, in practice. In theory you'd have to be more careful, but people have relied on weaker assumptions in math proofs. But for statements about super-mario, it's more than reasonable to assume.
  - nine_k 3y ago
    So, NP-hard means that it's either NP-complete (the hardest NP can get), or even harder than that. Pretty intuitive to me.
- beefield 3y ago
  > 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 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. 2. That obviously P!=NP. You just for example lose information before giving the problem to the solver, say, I'm thinking a float with n decimals, then I round it to nearest integer and ask you to find the float given the integer. I can check the guess in linear time as n increases, but your difficulty increases exponentially as n increases. I am pretty sure there is something in this problem that makes it a not legal P/NP problem, but I have no idea what. I have a couple of times tried to look for more formal definitions of P/NP, but the jargon goes immediately above my head. (The "guess" is admittably there a bit informal, if you want a bit more formal problem, you take a process C that is mathematically proven to be sufficiently sensitive to initial conditions (e.g. chaotic), take integer x and calculate y = C(x), round y and ask what's x.)
  - aatd86 3y ago
    Wait, how is it impossible to prove a negative?
    - beefield 3y ago
      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.
      - aatd86 3y ago
        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)
- globular-toast 3y ago
  You should grab a textbook about NP-completeness like Garey and Johnson. It's actually quite easy to understand and you can follow along some proofs for NP-completeness even if you don't have experience with that. NP-hard will follow.
- chriswarbo 3y ago
  I came across the example of the "bounded halted problem" recently, which I found quite intuitive for understanding P=NP https://www.lesswrong.com/posts/8Af3X8b7f5piqtqZx/computability-and-complexity#Bounded_halting https://www.lesswrong.com/posts/8Af3X8b7f5piqtqZx/computabil... We're given a program P of length n, let's say it's a Turing machine with binary symbols on its tape. We want to know if P halts in fewer than n steps for all inputs. Notice that only the first n bits of those inputs are relevant (since it would take n+1 steps to reach the n+1th bit, by which time we'd know it hasn't halted in fewer than n steps). Hence we can answer this in exponential time: run P(000...) for n steps to see if it halts, run P(100...) for n steps, run P(010...) for n steps, etc. There are ~2ⁿ bitstrings of length < n, so it takes O(n × 2ⁿ) steps to check all inputs. This problem is in NP, since we can check a candidate input in polynomial time, e.g. checking `P takes at least n steps on the input 01010101` requires running P on that input for at most n steps. It's also NP-complete since we can translate other NP problems into it (see the link for details) The reason I like this example is that it gives an intuition for how "overpowered" a polynomial solution to it would be: able to infer seemingly-arbitrary information about any program, without having to actually run them. This is similar to how an oracle for the (usual) halting problem could be used to quickly prove/disprove arbitrary mathematical statements, just by feeding it a dumb, brute-force proof searcher. (Of course, we could state the same more directly, since theorem proving is itself NP-complete: checking a proof of size n is easy, but finding one seems to require exponential time; however, that seems more abstract than the running of a program on inputs)
lambda 3y ago
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. But just because something is in P doesn't mean that you want to be solving it with a polynomial time algorithm on a regular basis.
- dwattttt 3y ago
  A terrific teardown of tracking down an unexpected O(n^2): https://randomascii.wordpress.com/2021/02/16/arranging-invisible-icons-in-quadratic-time/ https://randomascii.wordpress.com/2021/02/16/arranging-invis...
  - gdprrrr 3y ago
    Also reminds me of the GTA online case. https://news.ycombinator.com/item?id=26296339 https://news.ycombinator.com/item?id=26296339
  - chriswarbo 3y ago
    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 https://accidentallyquadratic.tumblr.com
    - loupol 3y ago
      Last post was made in 2019. (If you click on the name of the post it shows the timestamp at the bottom) Blog author stated on Reddit in 2021 that he wasn't maintaining it anymore[0]. [0] https://old.reddit.com/r/programming/comments/jdylxs/accidentally_quadratic/glbeiob/ https://old.reddit.com/r/programming/comments/jdylxs/acciden...
- fooker 3y ago
adrianN 3y ago
Look into the formal verification community, where PSPACE-complete is "easy" and undecidable is normal.
- quickthrower2 3y ago
  Hopefully they don’t need to deal with “big data”
withinboredom 3y ago
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 to solve this problem while n has grown over months or years, and some customers are hitting the tipping point and the app is crashing. So there's a lot of pressure to perform. That's what makes np-hard problems hard, imho; not the problem itself, but all the bullshit to get rid of it.
- imtringued 3y ago
  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 their head and everyone has to arrive at the same competitive equilibrium. That is what it takes to guarantee a competitive equilibrium. The thing is, if you have anything less than the competitive equilibrium, you lose the property of "free market supremacy" aka that markets are superior in every situation and that government intervention can never make anything better. So the NP hard problem has to be solved, you can't wiggle yourself out of this with an approximating solution. Any x%-approximation leaves a 100%-x% gap for something else to replace the free market. We now arrive in reality, where sometimes markets are really good and sometimes they are really bad, but that has not stopped people from worshipping Ayn Rand. The very same Ayn Rand that needed medical services provided by the government and therefore landed in the 100%-x% gap where markets aren't so nice any more. The by far dumbest part though, is that the economy in reality is an iterative process, not a static process that jumps from one competitive equilibrium to the next, and there are ways to use local rules and institutions to encourage arriving as close to equilibrium as possible but those are considered government intervention or against human nature or some other nonsense, even if they actually let markets be more "free" and with less government intervention overall. So you have these schizophrenic economists who argue in favor of unattainable competitive equilibria, while simultaneously sabotaging the arrival at close enough equilibria plus some government intervention as a fallback. The height of irony is that this results in the economy ending up in a strong disequilibrium, but disequilibrium is fine as long as the economy is growing. The moment growth stops, that disequilibrium will become more and more apparent over time. [0] https://en.wikipedia.org/wiki/Fisher_market#Fisher_markets_with_indivisible_items https://en.wikipedia.org/wiki/Fisher_market#Fisher_markets_w...
deleted 3y ago
[deleted]
ngruhn 3y ago
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“
- fooker 3y ago
  > 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.
  - ngruhn 3y ago
    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.
    - empath-nirvana 3y ago
      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.
- Legend2440 3y ago
  It's always about worst-case complexity; you may be able to solve typical problems much easier. This even applies to the halting problem, which is unsolvable in general but pretty easy for most real programs. But also, "pretty large" is relative. Wikipedia says the largest known exact solution for a traveling salesman problem is 85,900 nodes, which is not really that many.
red_admiral 3y ago
Isn't there some graph problem about finding cliques that is NP-hard (presumably NP-complete in the decision version) but that has an expected _constant_ time algorithm over the usual distribution of random graphs? I seem to remember the algorithm is something like "check a few samples at random, if that doesn't find what you're after then do exponential-time search" and the point is the chance that the samples don't find what you're after is exponentially small, because the thing you're looking for is so frequent.
- CaptainNegative 3y ago
  If you're allowing for some error probability, then the answer is trivially yes. For example, the NP-Complete problem of "does this graph have a clique of size sqrt(n)" is trivial over G(n, 1/2) random graphs, because the answer is No with overwhelming probability (something decaying exponentially in n or n^2). So you don't have to read the input before responding. If you're referring to Las Vegas style (always correct) algorithms, then I don't think something along those lines can work. Reading a constant number t bits from a G(n,p) random graph yields each possible event with the constant probability (1/2)^t. So the expected running time is still at least some (small) constant times that of the failure case, which is still exponential. Are you perhaps thinking of the average case problem Planted Clique, where the task is to distinguish between a "clean" random graph G(n, 1/2) and a "planted" one where we force some random set of, say, k=n^(1/3) vertices to induce a clique? While distinguishing a graph with a k-clique from one without one is NP-hard on general graphs, you can show that G(n, 1/2) graphs virtually never contain cliques as large as 3 log n, and hence brute force searching all 3 log n sized subsets of vertices for cliques (in subexponential time n^(3 log n)) will almost always lead you to the correct answer. And once you find a clique of size 3 log n, expanding it to n^(1/3) can be done quickly using a greedy algorithm.
  - red_admiral 3y ago
    It was years ago I studied the problem and I've lost my notes, but what you say makes sense.
metalim 3y ago
Same thing about "halting problem". The fact that it's unsolvable in general case, doesn't mean we can't solve it easily for 99.99999999% of all problems in the category
luc4 3y ago
> 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.
abetusk 3y ago
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.

128 points by stefanpie 3y ago

Hey, I vouched for your submission. Just wanted to let you know that there seems to be some issue with your account causing your submissions to be automatically flagged. You may want to contact HN moderators (hn@ycombinator.com) about that.

dang 3y ago
I've fixed it now. Thanks for watching out for a fellow user!

deleted 3y ago

[deleted]

vsnf 3y ago

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.

deleted 3y ago
[deleted]
- Ar-Curunir 3y ago
  For cryptography, every instance is (conjectured to be) complex, not just laborious. For worst-case NP-hardness, the complex instances are also laborious, while the simple instances are not laborious.
jandrese 3y ago
From what I remember: NP: Finding the solution takes more than polynomial time, but you can verify the answer is correct in polynomial time. NP-Hard: Finding the solution takes more than polynomial time, and it also takes more than polynomial time to verify that the solution is correct. NP-Complete: NP-Hard, but it can be transformed into any other NP-Complete problem in polynomial time. This is special because it means if you find a solution for any NP-Complete problem, you have found a solution for all of them. Finding an NP-Complete solution always seemed rather rather optimistic to me, but computer science professors obsessed over these problems. Caveat: It has been more than 20 years since I was quizzed on this stuff, so it might be wrong.
- quickthrower2 3y ago
  --Edit: this was wrong, see reply comment-- NP: you can verify the answer is correct in polynomial time. (and no other clauses) Anything in P is in NP
  - Dylan16807 3y ago
    I think it's worth saying what NP stands for. Nondeterministic Polynomial. Where "nondeterministic" basically means you get to try every single polynomial solution in parallel.
  - minitech 3y ago
    Not wrong, just a different criterion that describes the same complexity class.
  - raincole 3y ago
    > --Edit: this was wrong, see reply comment-- You're not wrong tho. NP problems can be verified in polynomial time. Nondetermisitic turnig machine is like a turing machine that has multiple "next steps" instead of one at a given time, and can migically choose the correct next step. You can think it as "taking all the possible paths at the same time (but at the end only the correct one matters)". But you can also think it as "given all the 'choices' it made, check if there is actually such a path", in other words, verifying a certification.
dandanua 3y ago
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 NP at all. Which is another confusing naming, because problems not in NP are NP-hard. As a saying goes, there are two main problems in programming - naming things and cache invalidation. And in this case the former fails badly.
- tgv 3y ago
  > 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 3y ago
    [deleted]
  - dandanua 3y ago
    And if P = NP any problem will be NP-hard. Until P ≠ NP is proved we can't heavily rely on the consequences.
    - tgv 3y ago
      That's an exaggeration. It's pretty safe to assume P ≠ NP, in practice. In theory you'd have to be more careful, but people have relied on weaker assumptions in math proofs. But for statements about super-mario, it's more than reasonable to assume.
- nine_k 3y ago
  So, NP-hard means that it's either NP-complete (the hardest NP can get), or even harder than that. Pretty intuitive to me.
beefield 3y ago
> 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 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. 2. That obviously P!=NP. You just for example lose information before giving the problem to the solver, say, I'm thinking a float with n decimals, then I round it to nearest integer and ask you to find the float given the integer. I can check the guess in linear time as n increases, but your difficulty increases exponentially as n increases. I am pretty sure there is something in this problem that makes it a not legal P/NP problem, but I have no idea what. I have a couple of times tried to look for more formal definitions of P/NP, but the jargon goes immediately above my head. (The "guess" is admittably there a bit informal, if you want a bit more formal problem, you take a process C that is mathematically proven to be sufficiently sensitive to initial conditions (e.g. chaotic), take integer x and calculate y = C(x), round y and ask what's x.)
- aatd86 3y ago
  Wait, how is it impossible to prove a negative?
  - beefield 3y ago
    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.
    - aatd86 3y ago
      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)
globular-toast 3y ago
You should grab a textbook about NP-completeness like Garey and Johnson. It's actually quite easy to understand and you can follow along some proofs for NP-completeness even if you don't have experience with that. NP-hard will follow.
chriswarbo 3y ago
I came across the example of the "bounded halted problem" recently, which I found quite intuitive for understanding P=NP https://www.lesswrong.com/posts/8Af3X8b7f5piqtqZx/computability-and-complexity#Bounded_halting https://www.lesswrong.com/posts/8Af3X8b7f5piqtqZx/computabil... We're given a program P of length n, let's say it's a Turing machine with binary symbols on its tape. We want to know if P halts in fewer than n steps for all inputs. Notice that only the first n bits of those inputs are relevant (since it would take n+1 steps to reach the n+1th bit, by which time we'd know it hasn't halted in fewer than n steps). Hence we can answer this in exponential time: run P(000...) for n steps to see if it halts, run P(100...) for n steps, run P(010...) for n steps, etc. There are ~2ⁿ bitstrings of length < n, so it takes O(n × 2ⁿ) steps to check all inputs. This problem is in NP, since we can check a candidate input in polynomial time, e.g. checking `P takes at least n steps on the input 01010101` requires running P on that input for at most n steps. It's also NP-complete since we can translate other NP problems into it (see the link for details) The reason I like this example is that it gives an intuition for how "overpowered" a polynomial solution to it would be: able to infer seemingly-arbitrary information about any program, without having to actually run them. This is similar to how an oracle for the (usual) halting problem could be used to quickly prove/disprove arbitrary mathematical statements, just by feeding it a dumb, brute-force proof searcher. (Of course, we could state the same more directly, since theorem proving is itself NP-complete: checking a proof of size n is easy, but finding one seems to require exponential time; however, that seems more abstract than the running of a program on inputs)

lambda 3y ago

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. But just because something is in P doesn't mean that you want to be solving it with a polynomial time algorithm on a regular basis.

dwattttt 3y ago
A terrific teardown of tracking down an unexpected O(n^2): https://randomascii.wordpress.com/2021/02/16/arranging-invisible-icons-in-quadratic-time/ https://randomascii.wordpress.com/2021/02/16/arranging-invis...
- gdprrrr 3y ago
  Also reminds me of the GTA online case. https://news.ycombinator.com/item?id=26296339 https://news.ycombinator.com/item?id=26296339
- chriswarbo 3y ago
  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 https://accidentallyquadratic.tumblr.com
  - loupol 3y ago
    Last post was made in 2019. (If you click on the name of the post it shows the timestamp at the bottom) Blog author stated on Reddit in 2021 that he wasn't maintaining it anymore[0]. [0] https://old.reddit.com/r/programming/comments/jdylxs/accidentally_quadratic/glbeiob/ https://old.reddit.com/r/programming/comments/jdylxs/acciden...
fooker 3y ago

adrianN 3y ago

Look into the formal verification community, where PSPACE-complete is "easy" and undecidable is normal.

quickthrower2 3y ago
Hopefully they don’t need to deal with “big data”

withinboredom 3y ago

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 to solve this problem while n has grown over months or years, and some customers are hitting the tipping point and the app is crashing. So there's a lot of pressure to perform. That's what makes np-hard problems hard, imho; not the problem itself, but all the bullshit to get rid of it.

imtringued 3y ago
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 their head and everyone has to arrive at the same competitive equilibrium. That is what it takes to guarantee a competitive equilibrium. The thing is, if you have anything less than the competitive equilibrium, you lose the property of "free market supremacy" aka that markets are superior in every situation and that government intervention can never make anything better. So the NP hard problem has to be solved, you can't wiggle yourself out of this with an approximating solution. Any x%-approximation leaves a 100%-x% gap for something else to replace the free market. We now arrive in reality, where sometimes markets are really good and sometimes they are really bad, but that has not stopped people from worshipping Ayn Rand. The very same Ayn Rand that needed medical services provided by the government and therefore landed in the 100%-x% gap where markets aren't so nice any more. The by far dumbest part though, is that the economy in reality is an iterative process, not a static process that jumps from one competitive equilibrium to the next, and there are ways to use local rules and institutions to encourage arriving as close to equilibrium as possible but those are considered government intervention or against human nature or some other nonsense, even if they actually let markets be more "free" and with less government intervention overall. So you have these schizophrenic economists who argue in favor of unattainable competitive equilibria, while simultaneously sabotaging the arrival at close enough equilibria plus some government intervention as a fallback. The height of irony is that this results in the economy ending up in a strong disequilibrium, but disequilibrium is fine as long as the economy is growing. The moment growth stops, that disequilibrium will become more and more apparent over time. [0] https://en.wikipedia.org/wiki/Fisher_market#Fisher_markets_with_indivisible_items https://en.wikipedia.org/wiki/Fisher_market#Fisher_markets_w...

deleted 3y ago

[deleted]

ngruhn 3y ago

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“

fooker 3y ago
> 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.
- ngruhn 3y ago
  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.
  - empath-nirvana 3y ago
    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.
Legend2440 3y ago
It's always about worst-case complexity; you may be able to solve typical problems much easier. This even applies to the halting problem, which is unsolvable in general but pretty easy for most real programs. But also, "pretty large" is relative. Wikipedia says the largest known exact solution for a traveling salesman problem is 85,900 nodes, which is not really that many.

red_admiral 3y ago

Isn't there some graph problem about finding cliques that is NP-hard (presumably NP-complete in the decision version) but that has an expected _constant_ time algorithm over the usual distribution of random graphs? I seem to remember the algorithm is something like "check a few samples at random, if that doesn't find what you're after then do exponential-time search" and the point is the chance that the samples don't find what you're after is exponentially small, because the thing you're looking for is so frequent.

CaptainNegative 3y ago
If you're allowing for some error probability, then the answer is trivially yes. For example, the NP-Complete problem of "does this graph have a clique of size sqrt(n)" is trivial over G(n, 1/2) random graphs, because the answer is No with overwhelming probability (something decaying exponentially in n or n^2). So you don't have to read the input before responding. If you're referring to Las Vegas style (always correct) algorithms, then I don't think something along those lines can work. Reading a constant number t bits from a G(n,p) random graph yields each possible event with the constant probability (1/2)^t. So the expected running time is still at least some (small) constant times that of the failure case, which is still exponential. Are you perhaps thinking of the average case problem Planted Clique, where the task is to distinguish between a "clean" random graph G(n, 1/2) and a "planted" one where we force some random set of, say, k=n^(1/3) vertices to induce a clique? While distinguishing a graph with a k-clique from one without one is NP-hard on general graphs, you can show that G(n, 1/2) graphs virtually never contain cliques as large as 3 log n, and hence brute force searching all 3 log n sized subsets of vertices for cliques (in subexponential time n^(3 log n)) will almost always lead you to the correct answer. And once you find a clique of size 3 log n, expanding it to n^(1/3) can be done quickly using a greedy algorithm.
- red_admiral 3y ago
  It was years ago I studied the problem and I've lost my notes, but what you say makes sense.

metalim 3y ago

Same thing about "halting problem". The fact that it's unsolvable in general case, doesn't mean we can't solve it easily for 99.99999999% of all problems in the category

luc4 3y ago

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

abetusk 3y ago

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.