10.9. Exercises
| 1: | Show that formula F = (v1) ∧ (v2 ∨ v3) ∧ (¬v3 ∨¬v1) is satisfiable, and justify that formula G = (v1) ∧ (v2 ∨ v3) ∧ (¬v3 ∨¬v1) ∧ (¬v2) is not. |
| 2: | Are there any other cliques in the graph of Figure 10-1? |
| 3: | Give a procedure for locating a clique of size n in any given graph. What is the time complexity of your algorithm? |
| 4: | An algorithm with a GUESS statement can be replaced by two clones of procedures executing the algorithm, one clone executing as if TRUE had been the correct guess, and the other executing as if FALSE had been correct. If one of these clones later encounters another guess, it clones itself again, so that two clones become three. Suppose an algorithm executes in n steps. What is a limit to the number of cloned processes ... |
Get Security in Computing, Third Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
