Computational Complexity
Computational complexity classifies problems by the resources required to solve them as input size grows. It defines classes like P, NP, and PSPACE, giving a framework for understanding which problems are tractable, which are hard, and what that hardness means in practice.
itComputer fundamentals | OpenSkills.info
Intro
Computational Complexity
Computational complexity asks how the resources needed to solve a problem grow as the input grows. Time is the most familiar resource. Memory, randomness, communication, and circuit size can matter too.
This subject gives you a map of computational difficulty. It helps you separate three questions:
- Can any algorithm solve the problem?
- If so, how much of a resource does an algorithm use?
- Can every algorithm be forced to use at least some amount of that resource?
The first question belongs to computability. Complexity theory focuses on the next two.
Problems, inputs, and resource models
A problem describes a required output for every valid input. An algorithm is a method for producing that output. Complexity attaches a cost to the algorithm as a function of input size.
Continue the course
This section is part of the paid course.
See pricing to subscribe, or log in if you already have access.
Sources
- https://xlinux.nist.gov/dads/HTML/bigOnotation.html
Supports
- Big-O is an asymptotic upper bound defined by fixed positive constants beyond a threshold
- Complexity measures depend on a model of computation and can cover time, memory, or other operations
- Constant factors and lower-order terms do not determine eventual growth
- https://xlinux.nist.gov/dads/HTML/asymptoticTimeComplexity.html
Supports
- Asymptotic time complexity describes limiting execution-time behavior as problem size grows
- https://xlinux.nist.gov/dads/HTML/npcomplete.html
Supports
- NP-complete decision problems belong to NP and are no easier than other NP problems under polynomial comparison
- NP membership can be described through polynomial-time certificate verification
- SAT and decision versions of several optimization problems are NP-complete examples
- https://xlinux.nist.gov/dads/HTML/nphard.html
Supports
- NP-hardness and NP-completeness are different labels
- An optimization problem can be NP-hard when its related decision problem is NP-complete
- https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/216b0252d29c797488da497a761716a4_MIT6_006F11_lec23.pdf
Supports
- P, NP, EXP, decision problems, certificates, hardness, completeness, and reductions form a basic complexity map
- P is contained in NP and P versus NP is open
- Reductions convert one problem into another and can transfer algorithms or hardness
- NP-complete problems are interreducible through polynomial-time reductions
- https://www.ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/resources/lecture-16-complexity-p-np-np-completeness-reductions/
Supports
- The MIT lecture and notes provide intermediate study of P, NP, NP-completeness, and reductions
- https://www.claymath.org/millennium/p-vs-np/
Supports
- P versus NP asks whether solutions that are quick to check are also quick to find
- P versus NP remains an outstanding unresolved problem
- Brute-force search can be infeasible even when a proposed solution is easy to verify
- https://www.claymath.org/library/monographs/MPPc.pdf
Supports
- P and NP are formally defined using deterministic and nondeterministic Turing machines and polynomial bounds in input length
- The P versus NP problem asks whether every language accepted nondeterministically in polynomial time is accepted deterministically in polynomial time
- Input length and the computation model are essential parts of a formal complexity statement
- https://cs.stanford.edu/~trevisan/cs254-10/
Supports
- Advanced complexity study includes P versus NP, hierarchy theorems, circuits, randomized classes, space classes, counting, pseudorandomness, and lower bounds
- https://cs.stanford.edu/people/trevisan/pcp/
Supports
- Approximation is one response to NP-hard optimization problems
- PCP results and reductions support proofs of inapproximability