Complexity Theory (Quick Summary)

Once we know a problem is "solvable" (Computable), this theory further studies how much Resource (Time and Space) is needed to solve it when the Input is very large.

1. Complexity Classes

Solvable problems are grouped by difficulty (in relation to time usage / Time Complexity):

• P (Polynomial Time): Problems that a Computer can solve quickly (e.g., Sorting, Searching, Shortest Path) O(n^k)
• NP (Nondeterministic Polynomial Time): Problems for which no one yet knows if they can be solved quickly, but if "someone provides the answer," a Computer can Verify its correctness quickly.

2. P vs NP Problem

This is one of the greatest mathematical mysteries of the millennium (Millennium Prize Problems).

• Question: "Can every problem whose answer can be verified quickly (NP) also be solved quickly (P)?" (Does P = NP?)
• Currently, most people believe that P ≠ NP (Solving the problem is inherently harder than verifying the answer).

3. NP-Completeness

The "hardest" group of problems in the NP Class.

• Properties: If someone finds a way to solve any single NP-Complete problem in Polynomial Time (P), all remaining problems in the NP group can instantly be solved at P speed! (Resulting in P = NP).
• Example problems: Traveling Salesman Problem (TSP), Boolean Satisfiability (SAT), Knapsack Problem.
• Applications: These problems are applied in Cryptography (e.g., RSA) because they involve concepts that are "very hard to solve, but very easy to verify." If systems could solve these problems in P time, all modern encryption in the world would collapse.