Ch.13: P and NP

Week 13 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 13.1. Time Complexity 13.2. The Class P 13.3. The Class NP

84 flashcards · Computer Science · by lakesare

Part of Textbooks › Automata, Formal Languages, and Turing Machines (Emre Sermutlu) · 14 courses

[Time Complexity] What is the time complexity of an algorithm?
A function f(n)f(n)f(n) : the maximum number of steps the algorithm uses on any input of length nnn . Time complexity is studied for deciders, i.e. algorithms that halt on every input.Example: searching for a key in an unsorted list of nnn items has time complexity nnn .
[Time Complexity] Does time complexity measure the running time on a clock?
No, time complexity counts operations. Hardware speed, access times and similar things are not taken into account.
[Time Complexity] Which case does time complexity describe: the best, the average or the worst?
The worst case. Example: a search for a key in an unsorted list of nnn items can end after 1 step if the key is first, but the time complexity is nnn .
[Time Complexity] f(n)f(n)f(n) and g(n)g(n)g(n) are functions. When is fff Big-Oh of ggg , written f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n)) ?
When there are constants ccc and n0n_0n0 with 0≤f(n)≤c g(n)0 \le f(n) \le c\,g(n)0≤f(n)≤cg(n) for all n≥n0n \ge n_0n≥n0 . Example: 2n2+8n+6=O(n2)2n^2 + 8n + 6 = O(n^2)2n2+8n+6=O(n2) , since 2n2+8n+6<5n22n^2 + 8n + 6 < 5n^22n2+8n+6<5n2 for all n≥4n \ge 4n≥4 .
[Time Complexity] Give constants ccc and n0n_0n0 that show 2n2+8n+6=O(n2)2n^2 + 8n + 6 = O(n^2)2n2+8n+6=O(n2) .
c=5c = 5c=5 , n0=4n_0 = 4n0=4 2n2+8n+6<5n2 ⟺ 3n2−8n−6>02n^2 + 8n + 6 < 5n^2 \iff 3n^2 - 8n - 6 > 02n2+8n+6<5n2⟺3n2−8n−6>0 , true for n≥4n \ge 4n≥4 . The values c=3c = 3c=3 , n0=9n_0 = 9n0=9 also work: the "best" values do not matter, only that some values work.Example: at n=4n = 4n=4 : 32+32+6=70<80=5⋅4232 + 32 + 6 = 70 < 80 = 5 \cdot 4^232+32+6=70<80=5⋅42 .
[Time Complexity] Is 2n2+8n+6=O(n3)2n^2 + 8n + 6 = O(n^3)2n2+8n+6=O(n3) correct?
Yes, but O(n3)O(n^3)O(n3) gives less information than O(n2)O(n^2)O(n2) . Big-Oh is only an upper bound, so any faster-growing ggg also works.
[Time Complexity] 8log⁡n+5n=O( ? )8 \log n + 5n = O(\,?\,)8logn+5n=O(?) (with log⁡=log⁡10\log = \log_{10}log=log10 ), and which ccc , n0n_0n0 show this?
O(n)\boldsymbol{O(n)}O(n) , with c=6c = 6c=6 , n0=10n_0 = 10n0=10 8log⁡n≤n8 \log n \le n8logn≤n for n≥10n \ge 10n≥10 , so 8log⁡n+5n≤6n8 \log n + 5n \le 6n8logn+5n≤6n .Example: at n=10n = 10n=10 : 8+50=58≤608 + 50 = 58 \le 608+50=58≤60 .
[Time Complexity] Which three changes to a function leave its Big-Oh class unchanged?
Adding a constant O(c+nk)=O(nk)O(c + n^k) = O(n^k)O(c+nk)=O(nk) Example: O(7+n2)=O(n2)O(7 + n^2) = O(n^2)O(7+n2)=O(n2) Multiplying by a constant O(c⋅nk)=O(nk)O(c \cdot n^k) = O(n^k)O(c⋅nk)=O(nk) Example: O(3n4)=O(n4)O(3n^4) = O(n^4)O(3n4)=O(n4) Adding a slower-growing function O(nk+nℓ)=O(nmax⁡(k,ℓ))O(n^k + n^\ell) = O(n^{\max(k, \ell)})O(nk+nℓ)=O(nmax(k,ℓ)) Example: O(n2+n5)=O(n5)O(n^2 + n^5) = O(n^5)O(n2+n5)=O(n5)
[Time Complexity] Give constants ccc and n0n_0n0 that show (n+1)2=O(n2)(n + 1)^2 = O(n^2)(n+1)2=O(n2) .
c=2c = 2c=2 , n0=3n_0 = 3n0=3 n2+2n+1≤2n2 ⟺ n2−2n−1≥0n^2 + 2n + 1 \le 2n^2 \iff n^2 - 2n - 1 \ge 0n2+2n+1≤2n2⟺n2−2n−1≥0 , true for n≥3n \ge 3n≥3 .Example: at n=3n = 3n=3 : 16≤1816 \le 1816≤18 ; at n=2n = 2n=2 : 9>89 > 89>8 .
[Time Complexity] Why are log⁡n\log nlogn , ln⁡n\ln nlnn and log⁡2n\log_2 nlog2n the same in Big-Oh notation?
Any two of them differ only by a constant factor. ln⁡n=ln⁡10⋅log⁡n\ln n = \ln 10 \cdot \log nlnn=ln10⋅logn , so ln⁡n=O(log⁡n)\ln n = O(\log n)lnn=O(logn) with c=ln⁡10c = \ln 10c=ln10 , n0=1n_0 = 1n0=1 ; and log⁡n≤ln⁡n\log n \le \ln nlogn≤lnn , so log⁡n=O(ln⁡n)\log n = O(\ln n)logn=O(lnn) with c=1c = 1c=1 .
[Time Complexity] Give constants ccc and n0n_0n0 that show 2n=O(n!)2^n = O(n!)2n=O(n!) .
c=1c = 1c=1 , n0=4n_0 = 4n0=4 From n=4n = 4n=4 on, each step multiplies n!n!n! by n+1≥2n + 1 \ge 2n+1≥2 and 2n2^n2n by 2.Example: 24=16≤24=4!2^4 = 16 \le 24 = 4!24=16≤24=4! , but 23=8>6=3!2^3 = 8 > 6 = 3!23=8>6=3! .
[Time Complexity] Give constants ccc and n0n_0n0 that show n4=O(2n)n^4 = O(2^n)n4=O(2n) .
c=1c = 1c=1 , n0=16n_0 = 16n0=16 Example: 164=216=6553616^4 = 2^{16} = 65536164=216=65536 ; at n=15n = 15n=15 : 154=50625>32768=21515^4 = 50625 > 32768 = 2^{15}154=50625>32768=215 .Likewise n8=O(2n)n^8 = O(2^n)n8=O(2n) with c=1c = 1c=1 , n0=48n_0 = 48n0=48 .
[Time Complexity] Rank these functions by growth rate: nlog⁡n, 2n, n, n!, log⁡n, nn, n2, n, n3, 1n \log n, \ 2^n, \ \sqrt{n}, \ n!, \ \log n, \ n^n, \ n^2, \ n, \ n^3, \ 1nlogn, 2n, n, n!, logn, nn, n2, n, n3, 1
1<log⁡n<n<n<nlog⁡n<n2<n3<2n<n!<nn\boldsymbol{1 < \log n < \sqrt{n} < n < n \log n < n^2 < n^3 < 2^n < n! < n^n}1<logn<n<n<nlogn<n2<n3<2n<n!<nn
[Time Complexity] How does binary search find an element xxx in a sorted array AAA ?
Compare xxx with the middle element A(mid)A(\mathit{mid})A(mid) : if A(mid)<xA(\mathit{mid}) < xA(mid)<x , continue in the right half; if A(mid)>xA(\mathit{mid}) > xA(mid)>x , in the left half; if equal, return mid\mathit{mid}mid . If the search range becomes empty, return NOT FOUND.
[Time Complexity] What is the time complexity of binary search in a sorted array of nnn elements?
O(log⁡2n)\boldsymbol{O(\log_2 n)}O(log2n) Each step halves the search range. If x=A(1)x = A(1)x=A(1) the search can end early, but the worst case counts.Example: a range of 1024 elements shrinks to 1 element after 10 halvings.
[Time Complexity] An algorithm checks whether all nnn elements of an array AAA are distinct by comparing A(i)A(i)A(i) with A(j)A(j)A(j) for all i<ji < ji<j . What is the time complexity?
O(n2)\boldsymbol{O(n^2)}O(n2) (n−1)+(n−2)+⋯+2+1=(n−1)n2(n-1) + (n-2) + \dots + 2 + 1 = \frac{(n-1)n}{2}(n−1)+(n−2)+⋯+2+1=2(n−1)n comparisons. The factor 12\frac1221 does not matter: two full loops i=1..ni = 1..ni=1..n , j=1..nj = 1..nj=1..n also take O(n2)O(n^2)O(n2) steps.Example: n=5n = 5n=5 gives 4+3+2+1=104 + 3 + 2 + 1 = 104+3+2+1=10 comparisons.
[Time Complexity] What is the time complexity of determining whether an element xxx occurs in an unsorted array of nnn elements?
O(n)\boldsymbol{O(n)}O(n) Compare xxx with A(1),A(2),…,A(n)A(1), A(2), \dots, A(n)A(1),A(2),…,A(n) in turn; in the worst case all nnn comparisons are needed.
[Time Complexity] An array of nnn elements is sorted by finding the smallest remaining element and swapping it to the front, in each iteration (selection sort). What is the time complexity?
O(n2)\boldsymbol{O(n^2)}O(n2) Iteration iii scans the n−in - in−i elements after position iii , which gives (n−1)+(n−2)+⋯+1=n(n−1)2(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}(n−1)+(n−2)+⋯+1=2n(n−1) comparisons.
[Time Complexity] What is the time complexity of this algorithm ( nnn a power of 2)? S=0S = 0S=0 , k=1k = 1k=1 . While k≤nk \le nk≤n : (for j=1j = 1j=1 to nnn : S=S+1S = S + 1S=S+1 ), then k=2kk = 2kk=2k .
O(nlog⁡2n)\boldsymbol{O(n \log_2 n)}O(nlog2n) The while loop runs about log⁡2n\log_2 nlog2n times ( k=1,2,4,…,nk = 1, 2, 4, \dots, nk=1,2,4,…,n ), each time with nnn operations.Example: n=8n = 8n=8 : k=1,2,4,8k = 1, 2, 4, 8k=1,2,4,8 , so 4⋅8=324 \cdot 8 = 324⋅8=32 operations.
[Time Complexity] What is the time complexity of this algorithm ( nnn a power of 2)? S=0S = 0S=0 , k=1k = 1k=1 . While k≤nk \le nk≤n : (for j=1j = 1j=1 to kkk : S=S+1S = S + 1S=S+1 ), then k=2kk = 2kk=2k .
O(n)\boldsymbol{O(n)}O(n) The inner loop runs 1+2+4+⋯+n=2n−11 + 2 + 4 + \dots + n = 2n - 11+2+4+⋯+n=2n−1 times in total.Example: n=8n = 8n=8 : 1+2+4+8=15=2⋅8−11 + 2 + 4 + 8 = 15 = 2 \cdot 8 - 11+2+4+8=15=2⋅8−1 .
[Time Complexity] Func1(n)\mathtt{Func1}(n)Func1(n) has complexity O(n)O(n)O(n) and Func2(n)\mathtt{Func2}(n)Func2(n) has complexity O(n2)O(n^2)O(n2) .What is the complexity of this algorithm? For i=1i = 1i=1 to 3n3n3n : ( Func1(i)\mathtt{Func1}(i)Func1(i) , Func2(i)\mathtt{Func2}(i)Func2(i) ). Then for j=1j = 1j=1 to nnn : Func1(n)\mathtt{Func1}(n)Func1(n) .
O(n3)\boldsymbol{O(n^3)}O(n3) Func1\mathtt{Func1}Func1 in the first loop: 1+2+⋯+3n=O(n2)1 + 2 + \dots + 3n = O(n^2)1+2+⋯+3n=O(n2) . Func2\mathtt{Func2}Func2 in the first loop: 12+22+⋯+(3n)2=O(n3)1^2 + 2^2 + \dots + (3n)^2 = O(n^3)12+22+⋯+(3n)2=O(n3) . Func1\mathtt{Func1}Func1 in the second loop: n+⋯+n=O(n2)n + \dots + n = O(n^2)n+⋯+n=O(n2) .Total: O(n2)+O(n3)+O(n2)=O(n3)O(n^2) + O(n^3) + O(n^2) = O(n^3)O(n2)+O(n3)+O(n2)=O(n3) .
[Time Complexity] Why is 12+22+⋯+n2=O(n3)1^2 + 2^2 + \dots + n^2 = O(n^3)12+22+⋯+n2=O(n3) , without using the exact formula?
There are nnn terms, each at most n2n^2n2 , so the sum is n⋅O(n2)=O(n3)n \cdot O(n^2) = O(n^3)n⋅O(n2)=O(n3) . The exact value is n(n+1)(2n+1)6\frac{n(n+1)(2n+1)}{6}6n(n+1)(2n+1) , but constants do not change the complexity class.
[Time Complexity] A password has nnn characters. How many operations does a brute-force search need if the characters are decimal digits, and if they are binary digits?
Decimal: O(10n)O(10^n)O(10n) . Binary: O(2n)O(2^n)O(2n) . Both are exponential running times. All possibilities have to be tried: 10n10^n10n resp. 2n2^n2n of them.
[Time Complexity] Printing all subsets of a set of nnn elements, where printing one subset is one operation: how many operations?
2n\boldsymbol{2^n}2n , an exponential running time One operation per subset: (n0)+(n1)+⋯+(nn)=2n\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n(0n)+(1n)+⋯+(nn)=2n .Example: n=3n = 3n=3 : 1+3+3+1=81 + 3 + 3 + 1 = 81+3+3+1=8 subsets.
[Time Complexity] What are the adjacency matrix and the adjacency list of a graph?
Matrix: rows and columns are the vertices, entries are the edges. List: each vertex has a list of its neighbors. The same directed graph as adjacency matrix and as adjacency list.
[Time Complexity] In a graph with nnn vertices, how many operations does checking for an edge between two given vertices take with an adjacency matrix, and with an adjacency list?
Matrix: O(1)O(1)O(1) . List: O(n)O(n)O(n) . The difference is polynomial, so the choice of representation does not matter for the classes studied here.
[Time Complexity] How does an algorithm check whether an undirected graph GGG is connected?
Starting from any vertex, mark all vertices reachable from it; GGG is connected exactly when every vertex is marked. Mark a vertex and push it on a stack SSS . While SSS is not empty: pop a vertex vvv , mark each unmarked neighbor uuu of vvv and push uuu on SSS .
[Time Complexity] Exploring a graph with a stack of vertices to visit is depth first search; with a queue instead of the stack it is breadth first search.
DFS and BFS.
[Time Complexity] A graph has nnn vertices and mmm edges. What is the time complexity of the stack-based connectivity check, with an adjacency matrix and with an adjacency list?
Matrix: O(n2)O(n^2)O(n2) . List: O(n+m)O(n + m)O(n+m) . The while loop runs at most nnn times. With a matrix, finding the neighbors of a vertex takes nnn operations each time; with lists, all iterations together look at each edge a constant number of times.
[Time Complexity] The DFS cycle-detection algorithm for directed graphs colors each vertex white, gray or black. What does each color mean?
White DFS(G,u)\mathrm{DFS}(G, u)DFS(G,u) has not been called yet for the vertex uuu . Gray DFS(G,u)\mathrm{DFS}(G, u)DFS(G,u) has started for the vertex uuu and is still running: DFS is still exploring the children of uuu . Black DFS(G,u)\mathrm{DFS}(G, u)DFS(G,u) has finished for the vertex uuu : all children of uuu have been explored. The main loop calls DFS(G,v)\mathrm{DFS}(G, v)DFS(G,v) for each vertex vvv that is still white.
[Time Complexity] The DFS cycle-detection algorithm colors a vertex gray while DFS is exploring its children, and black when that exploration is finished.When does the algorithm report a cycle in a directed graph, and why is that correct?
When a child www of the current vertex uuu is gray. A gray www is still being explored, so there is a path from www to uuu ; with the edge u→wu \to wu→w this gives a cycle.The complexity is O(n2)O(n^2)O(n2) with an adjacency matrix and O(n+m)O(n + m)O(n+m) with an adjacency list ( nnn vertices, mmm edges).
[The Class P] A deterministic single-tape TM decides {0n1n}\{0^n1^n\}{0n1n} by crossing off one 0 and then one 1, repeatedly. What is its time complexity?
O(n2)\boldsymbol{O(n^2)}O(n2) nnn iterations, each with O(n)O(n)O(n) moves across the tape.
[The Class P] How can a two-tape TM decide {0n1n}\{0^n1^n\}{0n1n} in O(n)O(n)O(n) steps?
Copy the 0s to the second tape in O(n)O(n)O(n) steps, then match them against the 1s in O(n)O(n)O(n) steps. A single-tape TM with the crossing-off method needs O(n2)O(n^2)O(n2) steps: running times depend on the computational model.
[The Class P] Running times depend on the model: deciding {0n1n}\{0^n1^n\}{0n1n} takes O(n2)O(n^2)O(n2) steps on a single-tape TM and O(n)O(n)O(n) on a two-tape TM. How does the theory treat such differences?
Polynomial differences in running time are considered unimportant. So both machines count as essentially the same algorithm, although the difference is very important in practice.
[The Class P] What is the class P\mathcal{P}P ?
The class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine. Example: {0n1n}∈P\{0^n1^n\} \in \mathcal{P}{0n1n}∈P , decided in O(n2)O(n^2)O(n2) steps.
[The Class P] Write P\mathcal{P}P as a union of the classes TIME(t(n))\mathrm{TIME}(t(n))TIME(t(n)) .
P=⋃k=0∞TIME(nk)\boldsymbol{\mathcal{P} = \bigcup_{k=0}^{\infty} \mathrm{TIME}(n^k)}P=⋃k=0∞TIME(nk) TIME(t(n))\mathrm{TIME}(t(n))TIME(t(n)) is the class of languages decided by a deterministic single-tape TM in O(t(n))O(t(n))O(t(n)) steps.
[The Class P] Why is the class P\mathcal{P}P important?
P\mathcal{P}P roughly corresponds to the algorithms that give results in reasonable time, i.e. to all useful computer programs.
[The Class P] An algorithm needs 1 hour for input size n=50n = 50n=50 . How long does it need for n=100n = 100n=100 if its complexity is O(n)O(n)O(n) , O(n2)O(n^2)O(n2) , O(n3)O(n^3)O(n3) , O(2n)O(2^n)O(2n) ?
2, 4 and 8 hours; but 2502^{50}250 hours for O(2n)O(2^n)O(2n) 250≈10152^{50} \approx 10^{15}250≈1015 hours (1 quadrillion), about 128 billion years.
[The Class P] Given nnn positive integers, find two distinct ones, ppp and qqq , with p+qp + qp+q as close as possible to 256. Why is the problem in P\mathcal{P}P ?
Checking all n(n−1)2\frac{n(n-1)}{2}2n(n−1) pairs takes O(n2)O(n^2)O(n2) steps. Keep the best pair so far and replace it whenever ∣A(i)+A(j)−256∣<∣p+q−256∣|A(i) + A(j) - 256| < |p + q - 256|∣A(i)+A(j)−256∣<∣p+q−256∣ .
[The Class P] Each of nnn students lists the classmates they ever worked with. Are there 3 students who pairwise worked together? Why is the problem in P\mathcal{P}P ?
There are (n3)=O(n3)\binom{n}{3} = O(n^3)(3n)=O(n3) triples, each checked in O(n)O(n)O(n) by going over the lists: O(n4)O(n^4)O(n4) in total. Example: n=30n = 30n=30 gives (303)=4060\binom{30}{3} = 4060(330)=4060 triples.
[The Class P] String matching problem: does a word of length kkk occur in a string of length nnn ( k≤nk \le nk≤n )? Why is the problem in P\mathcal{P}P ?
Try each of the n−k+1n - k + 1n−k+1 start positions and compare up to kkk characters: at most nk=O(n2)nk = O(n^2)nk=O(n2) steps. At the first mismatch, give up that start position and continue with the next one.
[The Class P] What is an Euler path in a graph GGG ?
A path that goes through each edge of GGG exactly once. Vertices may be visited more than once.
[The Class P] A graph GGG contains an Euler path from a vertex sss to a different vertex ttt if and only if … ?
GGG is connected, sss and ttt have odd degree, and all other vertices have even degree. These conditions can be checked in polynomial time, so the Euler path problem is in P\mathcal{P}P .
[The Class P] Find an Euler path in this graph. Where must every Euler path start and end?
1−3−5−2−4−1−2−31 - 3 - 5 - 2 - 4 - 1 - 2 - 31−3−5−2−4−1−2−3 ; every Euler path starts at 1 and ends at 3, or the reverse. 1 and 3 are the only vertices of odd degree (3 each); 2 has degree 4, and 4 and 5 have degree 2.
[The Class P] Why has this graph no Euler path?
Four vertices (1, 2, 3, 5) have odd degree; an Euler path allows at most two. Degrees: deg⁡1=deg⁡2=deg⁡3=deg⁡5=3\deg 1 = \deg 2 = \deg 3 = \deg 5 = 3deg1=deg2=deg3=deg5=3 , deg⁡4=2\deg 4 = 2deg4=2 .
[The Class P] What is a Hamiltonian path in a graph GGG ?
A path that goes through each vertex of GGG exactly once.
[The Class P] Is the Hamiltonian path problem in P\mathcal{P}P ?
Unknown. Brute force tries all n!n!n! orderings of the nnn vertices: not polynomial, even worse than exponential.
[The Class P] Find a Hamiltonian path in this graph.
1−2−3−6−5−4\boldsymbol{1 - 2 - 3 - 6 - 5 - 4}1−2−3−6−5−4 Each of the 6 vertices appears once, and each consecutive pair is joined by an edge.
[The Class P] Why has this graph no Hamiltonian path?
Three vertices (1, 3, 4) have degree 1, so each would have to be an end of the path, but a path has only two ends.
[The Class P] P\mathcal{P}P contains only decision problems. How is the shortest path problem ("which path between two given vertices has minimum total weight?") turned into a decision problem?
"Is there a path of weight less than WWW connecting the given vertices?" A decision problem has the answer Yes or No.
[The Class P] Is the decision version of the shortest path problem (directed graph, nonnegative weights) in P\mathcal{P}P ?
Yes: Dijkstra's algorithm runs in O(n2)O(n^2)O(n2) for nnn vertices with an adjacency matrix. Dijkstra's algorithm starts from the source vertex and finds the shortest distance to all vertices reachable in 1 step, then 2 steps, etc.
[The Class P] Find the shortest path from AAA to DDD and its weight.
A−F−C−DA - F - C - DA−F−C−D , weight 7 1+2+4=71 + 2 + 4 = 71+2+4=7 . Other paths: A−C−DA - C - DA−C−D has weight 11, A−B−C−DA - B - C - DA−B−C−D has 10, A−F−C−E−DA - F - C - E - DA−F−C−E−D has 10.
[The Class NP] What does NP\mathcal{NP}NP stand for?
Nondeterministic polynomial time.
[The Class NP] What are the two equivalent characterizations of NP\mathcal{NP}NP ?
Verifiers NP\mathcal{NP}NP is the class of languages that have polynomial time verifiers. Example: given a sequence of vertices, a verifier checks in polynomial time whether the sequence is a Hamiltonian path. Nondeterministic Turing machines NP\mathcal{NP}NP is the class of languages decided by some nondeterministic polynomial time Turing machine.
[The Class NP] What is the basic idea behind the class NP\mathcal{NP}NP ?
Verifying a given solution is much easier than finding a solution. Example: whether a graph has a Hamiltonian path is not known to be decidable in polynomial time, but a given Hamiltonian path can be checked in polynomial time.
[The Class NP] How does a polynomial time verifier give a nondeterministic polynomial time TM for the same language?
The NTM runs the verifier in every branch of its computation tree, each branch with a different candidate solution. Like the same program running on very many parallel computers, each with a different input, covering all possibilities.
[The Class NP] How does a nondeterministic polynomial time TM give a polynomial time verifier for the same language?
An accepting branch finds a solution in polynomial time; the choices made in that branch are given to the verifier, which repeats them deterministically.
[The Class NP] To show that a problem is in NP\mathcal{NP}NP , do you need to solve the problem?
No: you only need to verify a given solution in polynomial time.
[The Class NP] Coloring problem: given a graph with nnn vertices and an integer kkk , can the vertices be colored with kkk colors so that adjacent vertices get different colors? Why is the problem in NP\mathcal{NP}NP ?
A given coloring is verified by checking all n(n−1)2=O(n2)\frac{n(n-1)}{2} = O(n^2)2n(n−1)=O(n2) pairs of vertices: if a pair is adjacent and has the same color, reject. O(n2)O(n^2)O(n2) with an adjacency matrix, O(n3)O(n^3)O(n3) with adjacency lists; the difference is polynomial, so the problem is in NP\mathcal{NP}NP either way.
[The Class NP] What is a minimum spanning tree of a weighted, connected, undirected graph GGG ?
A subgraph that connects all vertices of GGG and has minimum total weight. A graph and a minimum spanning tree of it, of weight 3+1+2+5+7=183 + 1 + 2 + 5 + 7 = 183+1+2+5+7=18 .
[The Class NP] What is the decision version of the minimum spanning tree problem?
Given a weighted graph GGG and a number WWW , is there a spanning tree with weight ≤W\le W≤W ?
[The Class NP] How does Kruskal's algorithm find a minimum spanning tree?
Add edges one by one in order of increasing weight, skipping each edge that would create a cycle. So the minimum spanning tree problem can even be solved in polynomial time.
[The Class NP] Find a minimum spanning tree of this graph and its weight.
The edges of weight 1, 2, 3, 5, 7; total weight 18. Kruskal's algorithm: take 1, 2, 3; skip 4 (cycle); take 5; skip 6 (cycle); take 7. Then all 6 vertices are connected by 6−1=56 - 1 = 56−1=5 edges.
[The Class NP] Given a graph GGG with nnn vertices and a number WWW , how is a proposed spanning tree of weight ≤W\le W≤W verified in polynomial time?
Check that the n−1n - 1n−1 given edges are edges of GGG , that their weights add up to at most WWW , and that they connect all vertices (equivalently: form no cycle). Each edge is checked in O(1)O(1)O(1) (or O(n)O(n)O(n) ) steps. So the decision version of the minimum spanning tree problem is in NP\mathcal{NP}NP .
[The Class NP] Vertex cover problem: given a graph and an integer kkk , what is asked?
Is there a set of kkk vertices such that every edge has at least one end in the set? Such a set is a kkk -cover.
[The Class NP] Find a 3-cover of this graph. Why is there no 2-cover?
{v1,v4,v7}\{v_1, v_4, v_7\}{v1,v4,v7} . No 2-cover: the edges v4v5v_4v_5v4v5 , v1v2v_1v_2v1v2 , v3v7v_3v_7v3v7 have no common ends, so covering them needs 3 vertices.
[The Class NP] How is a proposed vertex cover of kkk vertices verified for a graph with nnn vertices and mmm edges?
Mark all edges at each of the kkk vertices, then reject if some edge is unmarked, otherwise accept. This takes O(n2)O(n^2)O(n2) steps, so the vertex cover problem is in NP\mathcal{NP}NP .
[Exercises] What is the time complexity of this algorithm? S=0S = 0S=0 . For i=1i = 1i=1 to nnn : for j=1j = 1j=1 to i2i^2i2 : S=S+jS = S + jS=S+j .
O(n3)\boldsymbol{O(n^3)}O(n3) 12+22+⋯+n21^2 + 2^2 + \dots + n^212+22+⋯+n2 steps: nnn terms, each at most n2n^2n2 .
[Exercises] What is the time complexity of this algorithm? S=0S = 0S=0 . For i=1i = 1i=1 to nnn : for j=ij = ij=i to 2n2n2n : for k=1k = 1k=1 to 202020 : S=S+1S = S + 1S=S+1 .
O(n2)\boldsymbol{O(n^2)}O(n2) The middle loop runs 2n−i+1≤2n2n - i + 1 \le 2n2n−i+1≤2n times, and the inner loop is a constant 20 steps.
[Exercises] What is the time complexity of this algorithm? S=0S = 0S=0 . For i=1i = 1i=1 to nnn : if iii is even, (for j=1j = 1j=1 to n2n^2n2 : S=S+1S = S + 1S=S+1 ), else S=S+10S = S + 10S=S+10 .
O(n3)\boldsymbol{O(n^3)}O(n3) About n2\frac{n}{2}2n even values of iii , each with n2n^2n2 steps: n32\frac{n^3}{2}2n3 .
[Exercises] What is the time complexity of multiplying two n×nn \times nn×n matrices with the standard textbook method?
O(n3)\boldsymbol{O(n^3)}O(n3) n2n^2n2 entries in the output, each a sum of nnn products: three nested for loops.
[Exercises] What is the time complexity of computing the determinant of an n×nn \times nn×n matrix by cofactor expansion?
O(n!)\boldsymbol{O(n!)}O(n!) Cofactor expansion reduces a problem of size nnn to nnn problems of size n−1n - 1n−1 , recursively down to size 1. (Better, polynomial algorithms for the determinant exist.)
[Exercises] Is the language of palindromes over Σ={a,b}\Sigma = \{a, b\}Σ={a,b} in P\mathcal{P}P ?
Yes: a given string can be checked in O(n2)O(n^2)O(n2) operations. e.g. a single-tape TM repeatedly compares and crosses off the first and the last remaining symbol.
[Exercises] Given n≥3n \ge 3n≥3 distinct positive integers, find the third largest. Time complexity, and is the problem in P\mathcal{P}P ?
O(n)\boldsymbol{O(n)}O(n) , so yes Three passes through the list (find and remove the maximum three times): 3n=O(n)3n = O(n)3n=O(n) operations.
[Exercises] Does an undirected graph with nnn vertices contain a rectangle, i.e. vertices A,B,C,DA, B, C, DA,B,C,D with edges A−BA - BA−B , B−CB - CB−C , C−DC - DC−D , D−AD - AD−A ? Why is the problem in P\mathcal{P}P ?
Checking all (n4)=O(n4)\binom{n}{4} = O(n^4)(4n)=O(n4) sets of 4 vertices is polynomial. (n4)=n(n−1)(n−2)(n−3)4!\binom{n}{4} = \frac{n(n-1)(n-2)(n-3)}{4!}(4n)=4!n(n−1)(n−2)(n−3) , and each set of 4 vertices has only 3 possible cyclic orders to check.
[Exercises] Given a set of nnn distinct positive integers, are there p,qp, qp,q in the set with p=q2p = q^2p=q2 ? Time complexity, and is the problem in P\mathcal{P}P ?
O(n2)\boldsymbol{O(n^2)}O(n2) , so yes Check all pairs (p,q)(p, q)(p,q) .
[Exercises] Subset-sum-zero problem: given a set SSS of nnn integers, does some (nonempty) subset add up to 0? Why is the problem in NP\mathcal{NP}NP ?
A given subset is verified in O(n)O(n)O(n) steps: add up its elements and compare with 0. Whether the problem is also in P\mathcal{P}P is not known.Example: {−12,28,7,−66,5}\{-12, 28, 7, -66, 5\}{−12,28,7,−66,5} : yes, −12+7+5=0-12 + 7 + 5 = 0−12+7+5=0 .
[Exercises] Does some subset of {9,18,−75,3,1,−40}\{9, 18, -75, 3, 1, -40\}{9,18,−75,3,1,−40} add up to 0?
No. The positive elements add up to only 9+18+3+1=319 + 18 + 3 + 1 = 319+18+3+1=31 , but the negative part of a subset is −75-75−75 , −40-40−40 or −115-115−115 .
[Exercises] Longest path problem (undirected weighted graph, simple paths only): what is the decision version, and why is it in NP\mathcal{NP}NP ?
"Is there a simple path of weight more than WWW connecting the given vertices?" A given path has at most n−1n - 1n−1 edges, so checking it takes polynomial time. A simple path is a path whose vertices are all distinct.
[Exercises] 0-1 knapsack problem: nnn items with weights wiw_iwi and values viv_ivi , and a knapsack of weight capacity WWW . What is the decision version, and why is it in NP\mathcal{NP}NP ?
"Is there a subset of items with weight ≤W\le W≤W and value ≥V\ge V≥V ?" A given subset has k≤nk \le nk≤n items, so checking it takes O(n)O(n)O(n) operations.
[Exercises] Traveling salesman problem: nnn cities with known distances. Is there a round trip through all cities, starting and ending at the same city, of total length less than LLL ? Why is the problem in NP\mathcal{NP}NP ?
For a given sequence of cities, add up the distances between consecutive cities and compare the sum with LLL : O(n)O(n)O(n) steps.
[Exercises] nnn courses are vertices; two courses are joined by an edge when some student takes both. Finals last 10 days. Can each course get a day k∈{1,…,10}k \in \{1, \dots, 10\}k∈{1,…,10} so that joined courses get different days? Why is the problem in NP\mathcal{NP}NP ?
For a given labeling, check for each course all its neighbors: O(n2)O(n^2)O(n2) operations. This is the coloring problem with k=10k = 10k=10 colors.
[Exercises] A clique is a subgraph in which every two vertices are joined by an edge. Does a graph with 2n2n2n vertices have a clique with nnn vertices? Why is the problem in NP\mathcal{NP}NP ?
A given set of nnn vertices is verified by checking its n(n−1)2=O(n2)\frac{n(n-1)}{2} = O(n^2)2n(n−1)=O(n2) pairs.
[Exercises] This graph has 6 vertices. Find a clique with 3 vertices.
{1,2,4}\boldsymbol{\{1, 2, 4\}}{1,2,4} (also {2,3,4}\{2, 3, 4\}{2,3,4} ) The edges 1−21 - 21−2 , 2−42 - 42−4 , 4−14 - 14−1 are all present.