Quiz 06 (April, 17th)

Statistics

There were 2 problems, each worth 10 points.

Problem 1

Formally define what is meant by TIME(t(n)).

Solution

A language L belongs to TIME(t(n)) if and only if there exists a Turing machine M that decides L and on each string x halts within O(t(n)) steps. (The constant hidden within the O notation is universal for all strings x.)

Problem 2

Given: A is polynomial-time mapping reducible to B, which is polynomial-time mapping reducible to C, and C is in NP.

What can you conclude about the membership in NP, and NP-completeness of A and/or C if B is known to be NP-complete? Briefly state reasons for your answers.

Solution

C is NP-complete. This is because, be assumption, it is in NP and an NP-complete problem B reduces to it. Thus, through B, all NP languages reduce to C.

A is in NP because it reduces to a language in NP. Nothing can be said about A other than that: It could be NP-complete, but it could be the empty set just as well.


April, 19th