NP-hard and NP-complete: These are terms from complexity theory, the field of mathematics that studies how hard it is to solve a given problem (as opposed to whether it can be solved at all, which is called “computability theory”). Other types of complexity include P, NP, PSPACE-complete, and EXPTIME-complete. Many abstract board games are classifiable as terms of their mathematical complexity in this way; for example, checkers is EXPTIME-complete, and Othello is PSPACE-complete. Rendering games obsolete is a favorite pastime of mathematicians. They have proven that for optimal players, the
...more
