(#015) Celeste is NP-Complete - Zeeshan Ahmed, Kunwar Shaanjeet Singh Grover
Date & Time: 28-11-2020, 22:15 IST
Abstract
Computers can solve a wide spectrum of problems, but they can't solve all the problems, some problems can never have a solution, some problems can be, but they require more space the size of the universe, or more time than the age of the universe on our computational models. So how do we measure such aspects of a problem? we do that using Complexity Theory, which deals with how and why a problem is harder than a different problem, and how to classify problems based on the resources they require.
Do Protein folding and sudoku have something in common? it might not seem so but Complexity Theory tells us that if we had an algorithm that could solve sudoku efficiently then we could adapt it to predict for protein folding. This same property is held by classic nintendo games such as super mario bros. We will demonstrate one such example where we prove how "Celeste" also shares such property by proving it to be NP-complete. And then later show how a small change in it makes the game much harder(Presumably) to compute; to be precise, PSPACE-complete.
Prerequisites
Asymptotic Notation (big-O), Boolean Algebra (Basic)
Resources
Nintendo games are computationally hard (A fun read)
Complexity - Introduction, Reductions