Helping a stranger, and why you should understand NP-complete

&gt; NP-complete is essentially shorthand for belonging to a class of problems that are computationally very hard<p>It&#x27;s totally correct, but it always bothers me a little to see people talk about NP in those terms; much, much more difficult problems are known. Recreational wikipedia reading taught me a while ago the the regexp equivalence problem (&quot;do these two given regular expressions define the same language?&quot;) is EXPSPACE-complete, where EXPSPACE contains all the problems that:<p>- Require additional space bounded above by an exponential function in the input.<p>- May require an unbounded (though obviously finite) amount of time.<p>That second point is a doozy, and the problem so accessible that I&#x27;m fairly sure many people have independently come up with it and wished for a solution. That&#x27;s not going to happen, though; a solution would be good for much more than just deciding whether two regexps are equivalent. Any NP-complete problem is utterly trivial by comparison.

<i>Think of NP-complete problems as if they were a brick wall like the red plot in the above graph. Understanding the theory behind the NP-complete complexity class means recognising intractable problems in your code – it’s like having a bomb sniffer dog when walking through a minefield.</i><p>Very helpful analogy - hadn&#x27;t thought of it like that. Now I&#x27;ll know whether the seemingly intractable problems in my code are only temporarily intractable due to my incompetence, or actually intractable for grander reasons :)

There&#x27;re few other things you can do to possibly speed up the second code snippet, by reducing dimensionality:<p>1) recognize q1 * q2 = 2^p1 * 2^p2 = 2^(p1 + p2), so instead of iterating over q1 then q2, iterate over p = p1 + p2<p>2) memorize some of the combinations; e.g. if you iterate over p, r1 &amp; r2, then you know that all you&#x27;re trying to find is two integers f1 &amp; f2 that are equal to output * r1 * r2 * 2^p &#x2F; input; so before you start solving the problem, calculate table T:<p><pre><code> for (int f1 = 1; f1 &lt;= 256; ++f1) for (int f2 = 1; f2 &lt;= 256; ++f2) T[f1 * f2] = f1 </code></pre> now you can check whether integer pair (f1,f2) exists, you can just check whether T[output * r1 * f2 * 2^p &#x2F; input] is non-zero. Also, output * r1 * r2 * 2^p has to be divisible by input, so after you iterate over p &amp; r1, you can iterate only over r2&#x27;s being multiples of input &#x2F; gcd(input, output * r1 * 2^p)<p>There could be possibly some more tricks found.

Here is one case where the original title would be significantly better than the title given:<p><pre><code> Helping a stranger (and why you should understand NP-complete)</code></pre>

<i>You have to be knowledgeable about a domain that can’t easily be simplified by series of web searches, and more importantly, there has to be a suggestion that someone might be seeking that clarification.</i><p>You won&#x27;t believe how difficult is to offer help if you are not a professional programmer of some sort (in HN and outside HN). Even for open source projects. Even if you try to provide insights on your &quot;professional&quot; job that, in theory, is full of &quot;startup potential&quot; (finance, like we are still using MS Access and messy spreadsheets).

&gt; They can tell you that the most efficient algorithm for ordering (randomised) data is Quicksort, which has a Big-O notation of O(nlogn)<p>I know this is nitpicky, but quicksort is, worst-case, O(n^2), meaning a large number of comparison based sorting algorithms are faster than it. Its in the average case that Quicksort wins.

This is actually a number theory problem. You want to have<p><pre><code> input * A = output * B (1) </code></pre> where<p><pre><code> A = f1 * f2 (2) B = r1 * r2 * q1 * q2 (3) </code></pre> where q1, q2 are powers of two.<p>Any good elementary number theory book will tell you that the smallest solution to (1) is to let M = lcm(input, output) and set A = M &#x2F; input, B = M &#x2F; output. Given the further constraint that A &lt;= 2^16, you can compute offline a 2^16 element lookup table which gives values of f1, f2 in the desired ranges for each possible value of A. You can re-use the same table to go from your B value to r1, r2 if you first pull out as many powers of two as you can and put them in q1, q2.

The first point of your definition of NP-completeness is backwards - every problem in NP must be reducible to the problem, not the other way round. The paragraph following the definition has it backwards, too.

Great post, I really enjoyed it. I wish there were more people with your skill set in my realm of expertise...it is amazing how many problems could be solved if they can be identified, classified, and attacked methodically like you just showed (instead of loosey-goosey hand-cobbled code). I can think of a few huge problems (big $$$) in my org that could be optimized really well if we had more people that could understand and apply constraint programming.