7. TIME COMPLEXITY Flashcards
How do we compute the running time of an algorithm Ð
As a function of the length of the string representing the input and don’t consider any other parameters.
What is asymptotic analysis?
One convenient form of estimation, where we seek to understand the running time of the algorithm when it is run on large inputs
The asymptotic notation is also called
big-O notation
Big-O notation has a companion called small-o notation. How does that work?
Big-O notation says that one function is asymptotically no more than another. To say that one func- tion is asymptotically less than another, we use small-o notation.
Polynomial time algorithms are fast enough for many purposes, but exponential time algorithms are rarely useful. Why is that ?
For example, let n be 1000, the size of a reasonable input to an algorithm. In that case, n^3 is 1 billion, a large but manageable number, whereas 2^n is a number much larger than the number of atoms in the universe.
Exponential time algorithms typically arise when we solve problems by exhaustively searching through a space of solutions, called ?
brute-force search.
All reasonable deterministic computational models are ?
polynomially equivalent.
What is P ?
P is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine.
The class P plays a central role in our theory and is important because
- P is invariant for all models of computation that are polynomially equivalent to the deterministic single-tape Turing machine, and
- P roughly corresponds to the class of problems that are realistically solv-
able on a computer.
A verifier for a language A is an algorithm V , where
A = {w| V accepts ⟨w, c⟩ for some string c}.
We measure the time of a verifier only in terms of the length of w, so a polynomial time verifier runs in polynomial time in the length of w. A language A is polynomially verifiable if it has a polynomial time verifier.
What is a certificate, or proof, of membership in A ?
A verifier uses additional information, represented by the symbol c in Defini- tion 7.18, to verify that a string w is a member of A. This information is called a certificate, or proof, of membership in A.
What is NP ?
NP is the class of languages that have polynomial time verifiers.
The term NP comes from ?
nondeterministic polynomial time
A language is in NP iff it is decided by some nondeterministic polynomial time
Turing machine.
We define the nondeterministic time complexity class NTIME(t(n)) as
analogous to the deterministic time complexity class TIME(t(n)).
P
the class of languages for which membership can be decided quickly
NP
the class of languages for which membership can be verified quickly.
The question of whether P = NP is one of the greatest unsolved problems in theoretical computer science and contemporary mathematics.
what are NP-complete problems
Certain problems in NP whose individual complexity is related to that of the entire class. If a polynomial time algorithm exists for any of these problems, all problems in NP would be polynomial time solvable.
A Boolean formula is satisfiable if some assignment of 0s and 1s to the variables makes the formula evaluate to ?
1.
A function f : Σ∗ −→ Σ∗ is a polynomial time computable function if some polynomial time Turing machine M exists that halts with just f (w) on its tape, when started on any input w.
Language A is polynomial time mapping reducible,1or simply polynomial time reducible, to language B, written A ≤P B, if
a polynomial time computable function f : Σ∗ −→ Σ∗ exists, where for every w,
w ∈ A ⇐⇒ f ( w ) ∈ B .
The function f is called the polynomial time reduction of A to B.
A language B is NP-complete if it satisfies two conditions:
- B is in NP, and
- every A in NP is polynomial time reducible to B.
