My good friend and computer scientest Kyle Burke has recently started a highly interesting blog on his research field: combinatorial game theory. The idea of this field is to use games as a tool for studying issues of complexity. Though his blog is only a month old, some important foundational ideas have begun to rear their heads, one of which I'll explore in this post.
Understanding complexity is important for almost any human endeavor, but defining it in rigorous terms is notoriously difficult. For example, which is the more complicated game, chess or tic-tac-toe? Almost anyone would say chess, but suppose you had a computer that was designed only to play chess. In fact, this computer has no capacity for calculation; it simply has the best move for any given chess position hardwired into its architecture. To get this computer to play tic-tac-toe, you would have to program it to translate each tic-tac-toe position into an analagous chess position, so it could then find the best chess move and translate this move back into tic-tac-toe. This computer would certainly find chess an easier game to play.
Computer scientists have a way around this paradox: instead of looking at individual games or problems, they look at classes of problems. Each problem in the class has a certain size, and they look at how complexity increases in relation to size.
For example, you could easily imagine playing tic-tac-toe on boards of various sizes. Computer scientists can analyze how the complexity of tic-tac-toe varies with the size of the board. (Chess, on the other hand, doesn't generalize as easily to larger sizes, which makes it difficult to talk about its complexity.)
Unfortunately, if we are faced with a real-world issue (such as how to provide for the needs of a large population), we will want to know the complexity of the specific problem at hand, not how the complexity might theoretically scale with problem size. Part of the reason that complexity issues are so often ignored (to the detriment of many well-meaning policies and programs) is that defining and quantifying complexity is so unavoidably slippery.
Further reading
- Home
- Angry by Choice
- Catalogue of Organisms
- Chinleana
- Doc Madhattan
- Games with Words
- Genomics, Medicine, and Pseudoscience
- History of Geology
- Moss Plants and More
- Pleiotropy
- Plektix
- RRResearch
- Skeptic Wonder
- The Culture of Chemistry
- The Curious Wavefunction
- The Phytophactor
- The View from a Microbiologist
- Variety of Life
Field of Science
-
-
Don't tell me they found Tyrannosaurus rex meat again!2 weeks ago in Genomics, Medicine, and Pseudoscience
-
-
-
Course Corrections4 months ago in Angry by Choice
-
-
The Site is Dead, Long Live the Site2 years ago in Catalogue of Organisms
-
The Site is Dead, Long Live the Site2 years ago in Variety of Life
-
Does mathematics carry human biases?4 years ago in PLEKTIX
-
-
-
-
A New Placodont from the Late Triassic of China5 years ago in Chinleana
-
Posted: July 22, 2018 at 03:03PM6 years ago in Field Notes
-
Bryophyte Herbarium Survey7 years ago in Moss Plants and More
-
Harnessing innate immunity to cure HIV8 years ago in Rule of 6ix
-
WE MOVED!8 years ago in Games with Words
-
-
-
-
post doc job opportunity on ribosome biochemistry!9 years ago in Protein Evolution and Other Musings
-
Growing the kidney: re-blogged from Science Bitez9 years ago in The View from a Microbiologist
-
Blogging Microbes- Communicating Microbiology to Netizens10 years ago in Memoirs of a Defective Brain
-
-
-
The Lure of the Obscure? Guest Post by Frank Stahl12 years ago in Sex, Genes & Evolution
-
-
Lab Rat Moving House13 years ago in Life of a Lab Rat
-
Goodbye FoS, thanks for all the laughs13 years ago in Disease Prone
-
-
Slideshow of NASA's Stardust-NExT Mission Comet Tempel 1 Flyby13 years ago in The Large Picture Blog
-
in The Biology Files
No comments:
Post a Comment
Markup Key:
- <b>bold</b> = bold
- <i>italic</i> = italic
- <a href="http://www.fieldofscience.com/">FoS</a> = FoS