The interesting open problem of the day comes from Pierre McKenzie. Consider a circuit that works on sets of nonnegative integers. Inputs are the sets {0} and {1}. The gates consist of union, intersection, complement, addition and multiplication. Addition of two sets A and B is the set consisting of x+y for x in A and y in B. Multiplication is similar.
Given such a circuit with specified input sets and an integer w, is it decidable whether w is in the set generated by the output gate?
A decision algorithm for this problem yields a way to settle Goldbach�s conjecture that every even number greater than 2 is the sum of two primes. I�ll leave this implication as an excercise.
No comments:
Post a Comment