Microsoft Word – hw2
COMS 4236: Introduction to Computational Complexity, Spring 2018
Problem Set 2, due Thursday February 22, 11:59pm on Courseworks
Please follow the homework submission guidelines posted on
Courseworks.
Problem 1. [20 points]
a. Let f(n)n be any nondecreasing function. Show that NTIME(f(n)) is closed under
union, intersection and concatenation. That is, if 1 2,L L are two languages in
NTIME(f(n)) then 1 2 1 2 1 2, and L L L L L L are also in NTIME(f(n)). Recall that the
concatenation of two languages 1 2,L L is 1 2 1 2{ | , }L L xy x L y L , i.e. the set of strings
that can be written as the concatenation of a string in 1L and a string in 2L .
b. The Kleene star of a language L is defined to be the set of all strings that can be written
as the concatenation of any number of (0, 1, or more) strings of L, i.e.
1 1{ | 0 and , , }
k kL x x k x L x L . For example, if L={a,ab,ba}, then (the
empty string), aba and ababa are in L* but abbba is not.
Show that NTIME(n) is closed under Kleene star, i.e. if LNTIME(n) then also L
NTIME(n).
Problem 2. [15 points] Use the theorems that we learned on the relations between
complexity classes to prove the following.
a. TIME(2n) TIME(22n)
b. NTIME(n2) SPACE(n3)
(Note: means that the left hand side is contained but is not equal to the right hand side.
Make sure to show both facts.)
Problem 3. [15 points]
a. An undirected graph G=(N,E) is called 3-colorable if its set N of nodes can be
partitioned into 3 disjoint subsets N1, N2, N3 (i.e. N1N2N3 = N) such that every edge
connects nodes in different subsets.
Show that the language 3-COLORABLE= { G | G is a 3-colorable graph } is in NP.
You can assume that a graph G is encoded as a string that gives its number n of nodes (in
binary), followed by a list of its edges, i.e. a sequence of pairs (u,v) of nodes, where each
node is a number (in binary) in {1,…,n}.
b. An undirected graph G=(N,E) is called bipartite (or 2-colorable) if its set N of nodes
can be partitioned into 2 disjoint subsets N1, N2 (i.e. N1N2 = N) such that every edge
connects nodes in different subsets. An equivalent characterization is given by the
following property: A graph is bipartite if and only if it does not contain a cycle with an
odd number of nodes. (You do not have to show this fact).
Show that the language BIPARTITE = { G | G is a bipartite graph } is in NL.
Problem 4. [15 points] Do Problem 7.4.4, parts (a,b,f) in the book. We reproduce the
problem below for convenience.
Problem 5. [20 points] Let A be an alphabet, # a symbol not in A, and N the set of natural
numbers. A padding function is a function pad: ( {#}) A N A defined as pad(w,l)
= # jw , where j=max(0, l-|w|); that is, if the length of a string w is less than l then we pad
it with enough #’s so that the resulting string has length l. For any language L A and
function : f N N define the language pad(L,f(m)) ={ pad(w,f(|w|)) | w L }.
a. Prove that a language L is in TIME( 2n ) if and only if pad(L, 2m ) is in TIME(n).
b. Argue similarly that L is in NTIME( 2n ) if and only if pad(L, 2m ) is in NTIME(n).
c. Prove that if TIME(n) = NTIME(n) then TIME( 2n ) = NTIME( 2n ).
(Note: This is an instance of a general translation property: Equality of complexity
classes translates upwards to higher resource bounds. You do not have to prove this.)
Problem 6. [15 points] Show that P ≠ SPACE(n).
(Hint: Assume P= SPACE(n). Use the space hierarchy theorem and a padding function to
get a contradiction.)
Note: We do not know how these two classes, P and SPACE(n), compare, i.e. if either
one contains the other (we believe neither does), but we know they are not equal.