COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University
Time Complexity
Copyright By PowCoder代写 加微信 powcoder
This lecture covers Chapter 10 of HMU: Time Complexity
Determinisitic Time Complexity Non-deterministic Time Complexity The classes P and NP
Additional Reading: Chapter 10 of HMU.
Time Complexity
A=0i1i |i∈NisaCFLanddecidable,e.g.byTMM1whichon input w:
1 Scan w and reject if anything not in {⊔, 0, 1} or 10 is found.
2 Repeat as long as there are 0s and 1s on the tape:
Scan across and replace with blanks both the leftmost 0 and the rightmost 1.
3 If either 0s or 1s are left reject, otherwise accept.
How much time does M1 need, as a function f of the length of the input word w?
Definition 1.1
The time complexity of a deterministic TM that halts on all inputs is the function
f : N −→ N, where f (n) is the maximum number of steps that M uses on any input of length n.
Example 1.2
For M1, it seems that f(2k) = f(2(k −1))+4k +3 for k > 1.
Asymptotic Notation (Big-O)
The exact running time function is often too complicated. The highest order terms dominate the function eventually, so we can ignore the other terms.
Definition 1.3
Letf,g:N−→R≥0 Saythatf(n)=O(g(n))ifthereexistc,n0 >0suchthatforall n ≥ n0
f(n)≤c·g(n) .
The function g is an (asymptotic) upper bound for f .
Bounds of the form nc for some c > 0 are called polynomial bounds; those of the form 2(nδ) are called exponential bounds when δ ∈ R is positive.
Examples 1.4
5n3 +2n2 +22n+6=O(n3) f from M1 is O(n2).
Big-O vs. log
We may safely omit the base of logarithms in the big-O notation because
logan=logbn . logb a
Small-o Notation
Definition 1.5
Letf,g:N−→R≥0 Saythatf(n)=o(g(n))if
lim f (n) = 0 .
n→∞ g(n) thatis,foranyc>0thereexistn0 >0suchthatf(n)
Verifying an answer is often much easier than finding it.
Definition 2.10
A verifier for a language A is an algorithm V , where
A={w | V accepts⟨w,c⟩forsomestringc}
We measure the running time of a verifier only in terms of the length of w, not that of the certificate (or proof) c. Language A is polynomially verifiable if it has a polynomial time verifier.
Examples 2.11
For HAMPATH a certificate for ⟨G,s,t⟩ could be the sequence of nodes forming a Hamiltonian path from s to t in G.
For COMPOSITES a certificate for ⟨x⟩ could be a non-trivial divisor of x.
Definition 2.12
NP is the class of languages that have polynomial time verifiers. Theorem 2.13
A language is in NP iff it is decided by some non-deterministic polynomial time TM. Proof.
“⊆:” guess the certificate.
“⊇:” use the accepting branch of the computation tree as certificate.
Definition 2.14
NTIME(t(n)) is the class of languages decided by an O(t(n)) time non-deterministic TM.
Corollary 2.15
NP = NTIME(nk ) k∈N
Example: Cliques
A clique in an undirected graph is a fully connected subgraph. A k-clique is a clique with k nodes.
CLIQUE = { ⟨G,k⟩ | Undirected graph G contains a k-clique }
The certificate is a (representation of a) k-clique.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com