Tuesday, January 07, 2003

Circuits over Sets of Natural Numbers

Last October I mentioned an open problem of Pierre McKenzie. In short, consider a circuit whose wires contain subsets of the natural numbers. Inputs are {0} and {1}. The gates consist of union, intersection, complement, addition and multiplication. For sets A and B, A+B = {x+y | x in A and y in B} and A×B = {xy| x in A and y in B}.

Is the following problem decidable: Given such a circuit for a set A and a natural number w, is w in A?

Here is the paper by McKenzie and Klaus Wagner that describes this problem and gives results for many subcases. It will appear in the upcoming STACS Conference.

I have been haunted by the simplicity of the question and the difficult of the solution. Let me give you the proof (which I left as an exercise in the earlier post) that a decision procedure for the problem would yield a way to determine Goldbach's conjecture that every even number greater than 2 is a sum of two primes.

Define the set GE2 (the numbers at least 2) as {0}∪{1}. Define PRIMES as GE2∩GE2×GE2. Define GOLDBACH as (GE2×2)∩( PRIMES+PRIMES). Now we have Goldbach's conjecture is true if only if 0 is not in {0}×GOLDBACH.

Since I don't think Goldbach's conjecture has an easy decision procedure, I don't believe there is a decision algorithm for the problem. Proving this seems very tricky. The obvious idea is to try and create Diophantine equations. But even generating the set of squares is open.

No comments:

Post a Comment