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.

Thank you for pointing me to this question. Beautiful and elegant indeed!

ReplyDeleteNutan