First of all – a quick explanation of P and NP. The class of problems known as ‘P’ – for polynomial (as in they can be solved in a time which is dependent on a polynomial of their complexity) – are those for which a known algorithm – a sequence of mathematical steps – to solve them exists. For instance, solving (i.e., finding the value of x where the formula evaluates to zero) x – 2 is a P class problem. NP (not P) problems are much more interesting – these are problems for which an algorithm exists but which is unknown at the time the problem is posed. In the worst case the only way of solving the problem may be to try all the potential algorithms until we find the one that solves the problem. That said, once a potential solution is found it can be verified ‘simply’ (i.e. in polynomial time). It is not known if, in fact NP problems (such as drawing up school timetables or cracking internet public key encryption) are really P type problems after all and we just have not found the solution or are permanently excluded from ‘simple’ (P) solutions. A class of NP problems called ‘NP complete‘ are those that, if shown to really be P class problems, would indicate P=NP. Most, but not all, mathematicians think, in fact P!=NP.
So, here’s the problem. It sounds simple, but as it is NP, it’s not! (I got this from Making Embedded Systems: Design Patterns for Great Software
You have a micro controller with a timer of fixed 4MHz frequency and two 8 bit registers, a and b, such that (a) counts ticks and (b) is a match register that triggers an interrupt when the count register matches the tick count stored and a 16 bit prescaler (that allows the scaling of the ticks e.g. – if set to 2 then twice as many ticks are required to trigger the interrupt).
So how can you set the match and prescaler to work for an arbitrary frequency? Sounds like it should be easily algorithmically managed, but it’s not.
Related articles
- how do you prove that SAT is NP-complete? (cs.stackexchange.com)
- Are there NP problems, not in P and not NP Complete? (cs.stackexchange.com)
- Rule of thumb to know if a problem could be NP-complete (cs.stackexchange.com)
cartesian product ... stuff about computing mostly 
3 responses to “An NP-complete problem from the world of embedded computing”
Just to be clear(er), problems in NP but not P typically can be solved by known algorithms. There are, however, no known algorithms whose run times are polynomial in the dimensions of the problem.
Paul, I have been thinking about your comment a lot – thinking it was wrong but as you are a professional, knowing that it could not be 🙂
Finally, today, I got the point (I think). These things are individually solved by an algorithmic procedure but there is no known algorithm to solve the problems per se. Hence one cannot say the problem can be solved in polynomial time as, in the end, one might have just use a brute force mechanism which might be solved on the first iteration or on the 20 billionth and so on… is that right?
Not exactly. Consider the knapsack problem, which is well described at https://en.wikipedia.org/wiki/Knapsack_problem. The optimization version (decide how to fill the knapsack) is NP-hard; the decision version (can a load be devised with value at least ?) is NP-complete. That means (a) if you give me a load you claim has value at least V, I can verify the claim in a time that is polynomial (in fact, linear) in the dimension of the problem; and (b) nobody (yet?) knows a way to find an optimal load in polynomial time.
Now I can apply a branch-and-bound algorithm (https://en.wikipedia.org/wiki/Branch_and_bound) to a knapsack model and be assured that, absent running out of time or memory, I will find an optimal load. It is considerably faster than brute force enumeration of all possible loads, but its worst case run time is not bounded by any polynomial function of the problem size. I think, though, that modern branch-and-bound solvers do quite well solving large instances of knapsacks (which occur frequently as subproblems or relaxations of more complex problems).
(Incidentally, most operations research people hear “problem size” and think “dimensions”, which in this case would be number of items; but technically I think it means total number of bits needed to encode all problem parameters, which for the knapsack would include item weights and values and the knapsack capacity.)
To summarize a bit, NP/NP-complete/NP-hard do not imply the lack of an “intelligent” algorithm (better than brute force); they just imply the lack (at least currently) of an algorithm whose run time is _guaranteed_ to be bounded by a polynomial function of problem size.