Introduction to Computational complexity theory - RPIQuantumComputing/QuantumCircuits GitHub Wiki

Computational complexity theory is a mathematical research area in which the goal is to quantify the resources required to solve computational problems. It is concerned with algorithms which are computational methods for solving problems.

Imagine you have a bunch of puzzles, each with its own level of difficulty. Some puzzles are easy to solve quickly, while others might take a lot more time and effort. Computational complexity theory helps us categorize these puzzles into different groups based on their difficulty.

Problem Classes

  • P: This class comprises decision problems that can be efficiently solved by a deterministic Turing machine in polynomial time. These problems are considered "easy" or "tractable" because they can be solved efficiently.

  • NP: Decision problems in this class allow for efficient verification of solutions in polynomial time. While finding the solution may be difficult, verifying its correctness is quick once provided.

  • NP-hard: Problems in this class are at least as challenging as the hardest problems in NP. They may lack efficient solutions but are as difficult as NP problems.

  • NP-complete: These decision problems reside in both NP and NP-hard. NP-complete problems are among the most challenging in NP, and if any of them have a polynomial-time algorithm, then all NP problems have such algorithms.

Complexity Measures

Computational complexity theory employs various measures to evaluate algorithm efficiency:

  • Time Complexity: This measure quantifies the time or number of steps required by an algorithm to solve a problem relative to the input size.

  • Space Complexity: It measures the memory space needed by an algorithm to solve a problem in relation to the input size.

  • Communication Complexity: This measure assesses the communication necessary between different computing entities (e.g., processors or machines) to solve distributed computing problems.

Additionally, computational complexity theory explores relationships between different complexity classes, such as containment relationships and completeness results. These insights help classify problems based on their computational complexity.

Overall, computational complexity theory plays a pivotal role in understanding algorithm capabilities and limitations. It guides the development of efficient algorithms and provides theoretical foundations for practical computing.