Open Problems

There was an interesting article about Einstein in The New Yorker, discussing his annus mirabilis, 1905, when he published a series of fundamental papers. One thing that was new to me in this article was that Einstein was inspired by a book by Henri Poincaré:

As it began, Einstein, twenty-five years old, was employed as an inspector in a patent office in Bern, Switzerland. Having earlier failed to get his doctorate in physics, he had temporarily given up on the idea of an academic career, telling a friend that “the whole comedy has become boring.” He had recently read a book by Henri Poincaré, a French mathematician of enormous reputation, which identified three fundamental unsolved problems in science. The first concerned the “photoelectric effect”: how did ultraviolet light knock electrons off the surface of a piece of metal? The second concerned “Brownian motion”: why did pollen particles suspended in water move about in a random zigzag pattern? The third concerned the “luminiferous ether” that was supposed to fill all of space and serve as the medium through which light waves moved, the way sound waves move through air, or ocean waves through water: why had experiments failed to detect the earth’s motion through this ether? Each of these problems had the potential to reveal what Einstein held to be the underlying simplicity of nature. Working alone, apart from the scientific community, the unknown junior clerk rapidly managed to dispatch all three. His solutions were presented in four papers, written in the months of March, April, May, and June of 1905.

Reading this inspired me to think about the importance of explicitly stated open problems. I soon came up with a list of examples of historically influential open problems:

1. Hilbert’s Problems
2. Clay Millennium Prize Problems
3. P versus NP
4. Poincaré’s Problems
5. Open Problems in Artificial Life
6. Longitude Problem
7. Ansari X Prize
8. Orteig Prize
9. Grainger Challenge Prize for Sustainability

Then I started looking for open problems in Artificial Intelligence:

1. Symbol Grounding Problem
2. Frame Problem
3. Frame + Symbol Grounding
4. Variable Binding Problem
5. Self-Reference and Self-Modifying Algorithms
6. Connection between Symbolic and Subsymbolic Cognition
7. Best Method for Knowledge Representation
8. Foundation of Unsupervised Learning
9. Integrating Multiple Models, Multiple Resolutions (Granularities), Multiple Senses (Modes)
10. Belief-Action-Desire Model
11. Approximate Database Retrieval
12. Ethical AI
13. Integrating the Subfields of AI
14. Learning Physical Skills
15. Credit Assignment Problem
16. Non-Monotonic Reasoning Problems
17. Problems with Negation as Failure
18. Common Sense
19. Learning Chess
20. Raj Reddy’s Problems and Grand Challenges
21. Grand Challenges

What would you add to this list?

Thanks to Martin Brooks and Daniel Lemire for discussions on this topic. I originally wrote the above notes to myself two years ago, but only remembered them after reading Daniel’s post.