With tax season here once again, I thought it would be a good time to present an interesting mathematical problem that could be worth one million dollars to whoever solves it. It is simple to present, but has stumped mathematicians for decades.

Let me begin with a review of logic circuits (although it can also be considered as mathematical operations with no connection to electronics). You begin with a set of "inputs" that can have a value of true or false. You can have as many or as few as you like. Then you apply a series of logic operations:
  • NOT: A single input is change from true to false, or from false to true
  • AND: Two inputs are compared, and if they are both true then it outputs "true"
  • OR: Two inputs are compared, and if either is true then it outputs "true"
  • NAND: Two inputs are compared, and if they are not both true, then it outputs "true"
  • XOR: Two inputs are compared and if only one is true, it outputs "true"
where each output of one logic operation is used as the input to the next one in the series, until only a single output is left. (In fact the computer that you are using right now is nothing more than billions of such logic operations, with the input provided by your keyboard/mouse/hard drive etc).

The problem is, given a specific series of logic operations, can you determine if any set of inputs will generate a true result? For simple arrangements of logic circuits, this is simply a matter of testing out all possible combinations. However when the circuit gets very large, it becomes increasingly difficult to determine the answer to that question.

In technical terms, the question is does there exist an algorithm which can determine the answer in polynomial time. Polynomial time means (roughly) that if I have N inputs, then the algorithm gives me an answer in time T = a + b N + c N^2 + d N^3 ... which is possible for a computer to do. If it is not polynomial time, then the time T grows as an exponential or worse, and it is not efficient (or often even possible) to do the calculation.

This problem is additionally important, as it can be proven that if a polynomial time solution exists for this problem, then it must exist for a larger collection of important problems in computing and applied mathematics. (If you want more details, look up the "P=NP" problem)

And that is why this problem is worth a million dollars. This simple question is connected to one of the famous Clay Millenium Problems in mathematics, and if anyone can solve it to the satisfaction of the mathematics community, they will win a one million dollar prize. That does tend to add a bit of excitement to this beautiful little mathematics problem...