|
Some computational problems are easy; others are hard. If you find a fast program for a problem, then you have have shown that the problem is easy. How can you show that a problem is hard? That is, how can you show that there is no clever program to solve a problem quickly? This is the goal of computational complexity theory.
Complexity theory lies at the intersection of computer science and mathematics. Although the material is highly theoretical, it has very practical consequences. For instance, when you buy something on-line, the financial transaction is encrypted for security; the supposed security of the transaction relies on unproven assumptions that a certain problem is computationally complex. Thus, the question of whether on-line financial transactions are secure is an important unsolved problem in computational complexity.
This project will not attempt to solve this famous problem, but will instead tackle some other questions that should help us improve our understanding of some important questions in computational complexity theory.
|
Sign in
to view more information about this project.
