Complexity Theory for Simpletons

@misc{citeulike:261262, abstract = {In this article, we shall describe some of the most interesting topics in the subject of Complexity Theory for a general audience. Anyone with a solid foundation in high school mathematics (with some calculus) and an elementary understanding of computer programming will be able to follow this article. First, we shall describe the P versus NP problem and its significance. Next, we shall describe two other famous mathematics problems, the Collatz 3n+1 Conjecture and the Riemann Hypothesis, and show how the notion of \"computational irreducibility\" is important for understanding why no one has, as of yet, solved these two problems.}, author = {Feinstein, Craig A. }, citeulike-article-id = {261262}, eprint = {cs.CC/0507008}, keywords = {complexity}, month = {Jul}, posted-at = {2005-10-22 09:07:34}, priority = {3}, title = {Complexity Theory for Simpletons}, url = {http://arxiv.org/abs/cs.CC/0507008}, year = {2005} }

TY - ELEC ID - citeulike:261262 L3 - citeulike-article-id:261262 N2 - In this article, we shall describe some of the most interesting topics in the subject of Complexity Theory for a general audience. Anyone with a solid foundation in high school mathematics (with some calculus) and an elementary understanding of computer programming will be able to follow this article. First, we shall describe the P versus NP problem and its significance. Next, we shall describe two other famous mathematics problems, the Collatz 3n+1 Conjecture and the Riemann Hypothesis, and show how the notion of "computational irreducibility" is important for understanding why no one has, as of yet, solved these two problems. TI - Complexity Theory for Simpletons KW - complexity AU - Feinstein, Craig PY - 2005/Jul/11/ UR - http://arxiv.org/abs/cs.CC/0507008 ER -