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.

On the site I can tell what's a verb and what's a noun (mostly), and I can understand some of the sentences... but oh. my. god. the things I don't know and will simply never be able to understand.

Here endeth the lesson.
12:42:21 AM    please comment []