Reference no: EM133277138

Theory of Computation

Question 1: Consider the language

HAMPATH = {G = (V, E), s, t | G is an undirected graph, s and t are vertices of G, and there exists a path from s to t that visits every vertex of G exactly once}

Show that this language is self-reducible.

Question 2: Consider the language

3-COLOR = { G | The vertices of graph G can each be labeled Red, Green or Blue such that no adjacent vertices have the same label}

Show that this language is self-reducible.

Question 3: (a) Define the languages (3-COLOR)‾, (HAMPATH)‾ and explain what is a succinct non-membership witness for these languages.

(b) Is the next language is coNP, PRIMES = {x | x is a prime number}? Explain your answer.

(c) You can search the internet to answer whether PRIMES is in P. Cite your source.

Question 4 Prove that language L' = {0^k1^k | k ≥ 0} is a member of class L.

Question 5 Consider the language

ODD-CYCLES = { G | G is an undirected graph that has an odd cycle}.

Give an algorithm that shows that this language is in NL.