NP-hard does not mean hard (2017)

Corollary: P does not mean easy.<p>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.<p>Now, sure, there are plenty of O(n^2) problems where the n stays small enough, or you don&#x27;t mind waiting or spending a ton of money on it. But just because something is in P doesn&#x27;t mean that you want to be solving it with a polynomial time algorithm on a regular basis.

In my experience, solving the NP-hard problem isn&#x27;t the part that is hard, it&#x27;s reducing the problem space and&#x2F;or solution space to make it into a P-problem (when n is sufficiently big enough to worry about it).<p>For example, changing how you&#x27;re storing the data in the first place, or talking to PM&#x2F;PO&#x27;s to learn if you really need an exact solution or if a very close approximation is ok.<p>Sometimes, you&#x27;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&#x27;s a lot of pressure to perform.<p>That&#x27;s what makes np-hard problems hard, imho; not the problem itself, but all the bullshit to get rid of it.

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&#x27;t get it? Anyway, after reading this article I feel like I&#x27;ve gotten one small step closer to filling in this gap in my CS knowledge.

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

Isn&#x27;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?<p>I seem to remember the algorithm is something like &quot;check a few samples at random, if that doesn&#x27;t find what you&#x27;re after then do exponential-time search&quot; and the point is the chance that the samples don&#x27;t find what you&#x27;re after is exponentially small, because the thing you&#x27;re looking for is so frequent.

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

I like to think about this in terms of &quot;ensembles&quot;, or a distribution on the problem instances you&#x27;re drawing from. NP-Hard talks about worst case in this set or distribution, even if the &quot;average&quot; or &quot;normal&quot; case is creating an instance that is &quot;easy&quot; to solve.<p>This is part of the problem of using technical terms in a lay context. &quot;Hard&quot; here talks about &quot;worst case hard&quot; or &quot;provably hard&quot; (via a reduction to 3-SAT). Whether a given instance of an NP-Complete problem that is drawn from an ensemble or distribution is &quot;intractable&quot; is a more subtle question.

&gt; 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.<p>I think they meant to say &quot;constant memory&quot; since every halting Turing Machine uses finite memory.

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

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.