Grand challenge problems refer to really difficult tasks that stretch the limits of cognitive ability. They are especially popular in high technology fields as working towards a solution often yields many new applications. Below are a list of some open problems, along with correlations to previously solved grand challenges.
Prove NP ≠ P
This is the holy grail of anyone working in theoretical computer science. Essentially the class P (set of all languages decidable by a deterministic Turing machine in polynomial time) is known to be a subclass of NP (set of all languages decidable by a nondeterministic Turing machine in polynomial time). But is it a proper subclass? A language L is said to be C-complete iff all languages within C reduce to L. This implies that if an NP-complete language were deterministically decidable in polynomial time, then all NP languages would be deterministically decidable in polynomial time. For example, the Traveling Salesman Problem would no longer require an exponential order of magnitude to compute.
It is generally believed today that no such NP-complete language exists. However, no one has actually proven this. This problem has gained so much attention that it is actually sponsored by the Clay Institute of Mathematics. The first person to solve this will win $1M, and probably get the Turing Award and Fields Medal as well.
While it does seem like an arduous task, other similarly difficult problems have been solved before. Perhaps the most famous open problem in mathematics was Fermat’s Last Theorem, which was eventually proved by Andrew Wiles. It only took 350 years.
Pass the Turing Test
The Turing test is that a computer’s responses in a text-based communications forum are indistinguishable from a human being’s. This is perhaps the holy grail of artificial intelligence researchers. The annual Loebner Prize recognizes the best advance towards this goal, though no one has won outright. This year’s award will in fact be announced the day of this blog posting.
This problem seems analogous to that of building a champion chess machine. This feat was accomplished by IBM through Deep Blue, which defeated world champion Garry Kasparov.
Put a Man on Mars
“They can put a man on the moon, but you still gotta eat your vegetables.” Sayings like this epitomize the sheer capability of the human race; we actually put a few members of our species on a different celestial body. Way to go NASA! The modern equivalent of this problem is to put a man on Mars.
Map the Human Proteome
With the complete map of the human genome, many began to wonder if it was possible to map the human proteome. There are many more proteins than protein-defining genes, so this is a much more difficult task.
