Fun Open Problems
."Mathematical Bugs" - problems which are easy to understand and seem very easy but are still open and are probably extremely difficult to resolve. [Disclaimer: my aim in putting these problems here is not to encourage anyone to work on these problems for a significant amount of time.]
Is there an algorithm which decides if the output of a circuit over subsets of the natural numbers outputs the empty set? Reference.
Is there a binary operation over the non-negative reals which satisfies the metric axioms and the group axioms? (Disclaimer: I don't know if this problem is actually open) Reference.
Is it true that for every finite union-closed family of sets, there is some x such that x is in at least half of the sets (in the family)? This is the Frankl Conjecture. Reference.
Given a list of integers x_1, x_2, x_3,..., x_n, and an integer k, how quickly can we decide if sqrt(x_1)+sqrt(x_2)+...+sqrt(x_n) < k? There is no known proof that this can be done in polynomial time... Reference.
Is there a binary operation over the non-negative reals which satisfies the metric axioms and the group axioms? (Disclaimer: I don't know if this problem is actually open) Reference.
Is it true that for every finite union-closed family of sets, there is some x such that x is in at least half of the sets (in the family)? This is the Frankl Conjecture. Reference.
Given a list of integers x_1, x_2, x_3,..., x_n, and an integer k, how quickly can we decide if sqrt(x_1)+sqrt(x_2)+...+sqrt(x_n) < k? There is no known proof that this can be done in polynomial time... Reference.