Complexity Theory Asign 1

2005 Paper 6 Question 12, parts a, b, e, f

Without looking at your notes, explain P, NP, and NP-complete

2002 Paper 5 question 12 part a

2001 Paper 6 question 12 part a and b

(From Sipser, problem 7.9)

Let CONNECTED = {<G> | G is a connected undirected graph}. Analyze the algorithm below to show that this language is in P

On input <G>, the encoding of a graph G:

1. Select the first node of G and mark it

2. Repeat the following stage until no new nodes are marked

3. For each node in G, mark it if it is attached by an edge to a marked node

4. Scan all nodes of G to determine whether they are already marked. If they are, accept, otherwise reject.