Super Mario is NP-Complete

Apparently, Super Mario is NP-complete. Zelda is PSPACE-complete.

Conclusion: Games are hard. Alternatively, we can all play games to solve hard problems in a fun way…

Possible Outcomes of P-NP

Russel Impagliazzo‘s great article on possible outcomes of P-NP

The Status of P versus NP Problem

The Status of P versus NP Problem (as of September 2009), by Lance Fortnow