Complexity Flashcards
(37 cards)
What does computational complexity measure?
The number of steps a Turing machine takes to compute an output.
How is complexity formally defined?
As the number of steps a Turing machine implementation of an algorithm takes before halting.
What is the time complexity of a machine that deletes all input symbols aⁿ?
C(n) = 2n + 1
What is the time complexity of a machine that checks if aⁿ is even or odd?
C(n) = n + 1
Why is the initial definition of TM complexity problematic?
Because TMs might not halt, vary across inputs of same length, and are sensitive to implementation details.
How do we fix non-halting machines in complexity theory?
Restrict attention to total computable functions (TMs that halt on all inputs).
How do we handle variation between inputs of the same length?
Use worst-case time complexity: C_M(n) = max steps for all |w| = n.
How do we handle differences in low-level implementation?
Use Big-O notation to abstract away constant and linear differences.
What does f(n) = O(g(n)) mean?
There exist constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀.
Why use Big-O notation in complexity?
To express machine-independent growth rates of time requirements.
What is the formal definition of time complexity of a decision problem?
A language L has time complexity O(g(n)) if some TM decides L and halts in ≤ O(g(n)) steps on inputs of length n.
What is worst-case time complexity?
The maximum number of steps a machine takes on any input of a given length.
What is average-case time complexity?
The expected number of steps taken on a randomly chosen input.
What is space complexity?
The number of tape cells used by a Turing machine on a given input.
What does it mean for a TM to be total?
It halts on all possible inputs — required for complexity analysis.
What is an example of a language with O(n²) complexity?
Palindrome checking: L = { w | w = w^R }
Why is palindrome checking O(n²)?
Because each comparison step may involve a scan across the whole string, summing to n(n+1)/2.
What is the benefit of using Big-O over raw step counts?
It abstracts away constant factors and minor variations for generality and comparison.
What does the complexity class P represent?
The class of problems that can be decided by a deterministic Turing machine in polynomial time.
What does it mean for a problem to be in P?
It can be solved efficiently — in O(n^d) time for some d ≥ 0.
What are some common time complexity classes?
O(1), O(log n), O(n), O(n²), O(n^d), O(2^n), O(n!)
Is primality testing in P?
Yes — the AKS algorithm showed it can be done in polynomial time.
What breakthrough occurred in 2004 related to primality?
Agrawal, Kayal, and Saxena proved that primality is in P (PRIMES is in P).
What is the TSP (Travelling Salesperson Problem)?
Find whether a tour visiting all cities once with total cost ≤ L exists.
