---
title: "complexity theory"
type: concept
related: [Complexity Theory]
source: https://www.jemoka.com/posts/kbhcomplexity_theory/
confidence: high
status: active
---

complexity theory is a theory in algorithms to analyze time classes.
older Notes We know that \(O(n\ log\ n)\) is between \(O(n)\) and \(O(n^2)\) &mdash; so we can roughly call it &ldquo;polynomial time.&rdquo;
Since the optimal comparison cannot be faster than polynomial time, we say that comparison-based sorting is a polynomial-time algorithm.
From this information, we can come up with two main time classes: \(P\) for solutions with known polynomial time, \(NP\) for non-deterministic polynomial time.
Think of it as \(P\) is solvable with polynomial time and \(NP\) is verifiable with polynomial time.
The cool thing about \(NP\) problems is that solving a subset of them (&quot;\(NP\) hard&quot; problems) solves all \(NP\) problems.
reduction (algorithms) reduction is how you can use \(NP-hard\) problems to solve all \(NP\) problems in complexity theory.
Say, multiplication:
say you have a basic algorithm to add we can perform multiplication by asking our black box addition algorithm to add \(n\) times in complexity theory terms, this means addition is &ldquo;at least as hard&rdquo; as multiplication. Because, if we can solve any addition problem, we can solve any multiplication problem. &ldquo;Given this, do that.&rdquo;
problem classes (see above)
&ldquo;Polynomial time&rdquo; \(P\) &mdash; problems solvable with polynomial time &ldquo;Non-deterministic polynomial time&rdquo; \(NP\) &mdash; problem verifiable with polynomial time &ldquo;Exponential time&rdquo; \(EXPTIME\) &mdash; problems that can only be solved in exponential time &ldquo;2 Exponential time&rdquo; \(2EXPTIME\) &mdash; class of problems that takes \(2^{2^n}\) time to solve Space complexity works in a similar way.
\(P\) and \(NP\) are deterministic and non-deterministic in context to a Turing machine.
Fundamentally, \(P\) and \(NP\) only apply to decision problems&mdash;given a problem, output &ldquo;yes&rdquo; or &ldquo;no.&rdquo; However, this definition can be stretched: sorting is a decision problem, because it can be stated as &ldquo;given an unsorted array, can you verify whether or not an array is sorted&rdquo;
