News for hackers. Stuff that matters.
Re:A CP Solution for XKCD NP Complete Restaurant Order by gkatsi on Tuesday May 28, 2013 @01:14PM (#5781210)
It is NP-complete in the weak sense: the reduction from, say, CNF-SAT, introduces very large coefficients (in the order of 2^n). The pseudo-polynomial algorithm has complexity linear in the magnitude of the coefficients, not in the size of their binary representation (hence pseudo). If the coefficients are small, that algorithm is efficient. See: http://en.wikipedia.org/wiki/Pseudo-polynomial_time

There are no comments on this comment yet.