首页 >
> 详细

CSCC63 Assignment 2

Induction and Recursive Definitions

Due 11:59pm, March 6

Warning: Your electronic submission of a PDF to Crowdmark (through Quercus) affirms that this as-

signment is your own work and no one else’s, and is in accordance with the University of Toronto Code of

Behaviour on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism

in CSCC63. Note that using Google or any other online resource is considered plagiarism.

1. (10 marks) Let INFINITE =

{〈M〉 ∣∣ |L(M)| =∞}. Show that INFINITE is neither recognizable nor

co-recognizable by proving that ALLTM 6mINFINITE.

Solution:

Let w1, w2, . . . be an effective enumeration of Σ

∗.

Let P = “On input 〈M〉:

1. Let M0 = “On input 〈x〉:

1. For wi = w1 to w|x|:

2. Run M on wi.

3. Accept.”

2. Return 〈M0〉.”

Proof that 〈M〉 ∈ ALLTM iff 〈M0〉 ∈INFINITE:

⇒) Suppose that 〈M〉 ∈ ALLTM :

⇒ M halts on every input.

⇒ M halts on the strings w1 to wk for every k ∈ N.

⇒ M halts on the strings w1 to w|x| for every input 〈x〉 to M0.

⇒ M0 accepts every input.

⇒ |L(M0)| =∞.

⇒ 〈M0〉 ∈INFINITE.

⇐) Suppose that 〈M〉 /∈ ALLTM :

⇒ There is some wk on which M loops.

⇒ There is some input x0 to M0 such that |x0| = k. M will then loop on the input w|x0|.

⇒ For all inputs x longer than x0, M0 will eventually try to run M on wx0 in line 2, and will

loop.

⇒ |L(M0)| < |x0|Σ|x0|

(This is an upper bound on the number of strings of length x0 — the extra factor is a quick

way of dealing with the possibility of a unary alphabet.)

⇒ |L(M0)| <∞.

⇒ 〈M0〉 /∈INFINITE.

1

2. (20 marks) Let L =

{〈M〉 ∣∣∃n ∈ N,M does not return n2 when run on 〈n〉}. Determine whether L is

decidable, recognizable, co-recognizable, or neither. Prove your answer without using Rice’s theorem.

Solution:

L is neither recognizable nor co-recognizable. We have two proofs below.

The easy way:

We’ll reduce from ALLTM . Since ALLTM is neither recognizable nor co-recognizable, this

will tell us immediately the L is also neither recognizable nor co-recognizable.

Let P = “On input 〈M〉:

1. Let M0 = “On input 〈n〉:

1. Run M on 〈n〉.

2. Return n2.”

2. Return 〈M0〉.”

Proof that 〈M〉 ∈ ALLTM iff 〈M0〉 ∈ L:

⇐) Suppose that 〈M〉 /∈ ALLTM :

⇒ M halts on every input.

⇒ For every n ∈ N, M halts on 〈n〉.

⇒ For every n ∈ N, M0 reaches step 2 and outputs n2.

⇒ 〈M0〉 /∈ L.

⇒) Suppose that 〈M〉 ∈ ALLTM :

⇒ There is some n0 on which M loops.

⇒ For this n0, M0 will loop in step 1, and so will not reach step 2.

⇒ For this n0, M0 will not output n20.

⇒ 〈M0〉 ∈ L.

The slightly longer way:

We could also just repeat the reductions to ALLTM from class, with minor modifications:

Proof that L is not recognizable (HALT 6m L):

Let P = “On input 〈M,w〉:

1. Let M0 = “On input 〈n〉:

1. Run M on 〈w〉.

2. Return n2.”

2. Return 〈M0〉.”

Proof that 〈M,w〉 ∈ HALT iff 〈M0〉 ∈ L:

⇐) Suppose that 〈M,w〉 ∈ HALT:

⇒ M halts on w.

⇒ For every n ∈ N, M0 reaches step 2 and outputs n2.

⇒ 〈M0〉 /∈ L.

⇒) Suppose that 〈M〉 /∈ HALT:

⇒ M loops on w.

⇒ M0 will never reach step 2 for any input 〈n〉.

⇒ M0 will not output n2 for any input 〈n〉.

⇒ 〈M0〉 ∈ L.

2

Proof that L is not co-recognizable (HALT 6m L):

Let P = “On input 〈M,w〉:

1. Let M0 = “On input 〈n〉:

1. Run M on 〈w〉 for n steps.

2. If it halts loop, otherwise return n2.”

2. Return 〈M0〉.”

Proof that 〈M,w〉 ∈ HALT iff 〈M0〉 ∈ L:

⇐) Suppose that 〈M,w〉 ∈ HALT:

⇒ M loops on w.

⇒ For every n ∈ N, M does not halt on 〈w〉 in n steps.

⇒ For every n ∈ N, M0 reaches step 2 and outputs n2.

⇒ 〈M0〉 /∈ L.

⇒) Suppose that 〈M〉 /∈ HALT:

⇒ M halts on w.

⇒ There is some n0 such that M halts on w in n0 step.

⇒ For this n0, M0 will loop in step 2.

⇒ For this n0, M0 will not output n20.

⇒ 〈M0〉 ∈ L.

3. (10 marks) Suppose that, for two languages A and B, A 6m B. If A is recognizable and the mapping

reduction is surjective, prove that B is also recognizable.

Solution:

Suppose that A 6 B, and that the mapping is surjective.

Then, there is some computable function f such that ∀x, x ∈ A↔ f(x) ∈ B.

Moreover, since the mapping is surjective, we know that for every y ∈ B, there is some x ∈ A

such that f(x = y), and for every y /∈ B, there is some x /∈ A such that f(x = y)(*).

Suppose further that A is recognizable. Then we know that the elements of A can be effectively

enumerated.

Let x1, x2, . . . be an effective enumeration of A.

We can write the following recognizer for B:

Let RB = “On input 〈y〉:

1. For i = 1 to ∞:

2. If f(xi) = y, accept.”

If y ∈ B, then there is some x ∈ A such that f(x) = y, by (*). Since A is recognizable, there is

some i ∈ N such that x = xi. Since f is computable, every loop iteration in RB will eventually

halt, and so RB will eventually reach this xi and accept.

If y /∈ B, then there is no x ∈ A such that f(x) = y, and so RB will never accept.

4. (10 marks) Show the class NP is closed under the Kleene star operation.

Solution:

Suppose that we have some L ∈ NP. Then there is a polytime verifier V such that, for every

x ∈ Σ∗, there is a polysize certificate Cx that V accepts iff x ∈ L.

Note that our indices in questions 2 and 3 are for the breaks between letters, not for the letters

themselves. That’s why they go from 0 to n, not n− 1.

3

To show L∗ ∈ NP, we say:

1. This is a decision problem.

2. If x ∈ L∗, then it is either empty, or it can be broken into substrings w1, . . . , wk such that

every wi ∈ L. If it is empty, we can verify it quickly, so we just need a certificate for non-empty

x.

If x 6= ε, the certificate C is:

• A set of indices showing where to break x into the substrings w1, . . . , wk.

• A set of certificates Cw1 , . . . , Cwk for L such that Cwi shows that wi ∈ L.

3. If |x| = n, then we can break x into at most n substrings. So we need to store at most n

indices and L certificates. Since each Cwi is polynomial in size, each is of size O(|wi|r) for

some r ∈ N. So the total size of the certificate is O(nr+1), and so the entire certificate is

polysize.

4. In order to verify the certificate, we use the following algorithm:

Let V ′ = “On input 〈x,C〉:

1. If x = ε, accept.

2. Else:

3. For i ∈ [1, . . . k]:

4. Run V on 〈wi, Cwi〉.

5. If it rejects, reject.

6. Accept.”

5. As we saw in the certificate, we only have to worry about k ≤ n, and so we have O(n)

iterations of the loop. Since V is a polytime verifier, it runs in O(nr′) time for some r′ ∈ N.

So each loop iteration takes O(|wi|r′) = O(nr′) time. The other operations are all constant

time, so the entire program takes O(nr′+1) time.

So L∗ ∈ NP.

5. (10 marks) Show the class co-NP is closed under the Kleene star operation.

Solution:

Suppose that we have some L ∈co-NP. So we know that L ∈ NP, and we want to show that(

L∗

) ∈NP.

The language

(

L∗

)

is the set of x such that, for all partitions of x into substrings w1, . . . , wk, at

least one of the wi is in L.

Since L ∈ NP, there is a polytime verifier V such that, for every x ∈ Σ∗, there is a polysize

certificate Cx that V accepts iff x ∈ L.

1. This is a decision problem.

2. The certificate C will be:

• A set S of pairs (i, j) of indices of x such that 0 ≤ i < j ≤ n for every i, j.

• A set Cxi:j of certificates for every substring xi:j of x whose indices are in S.

3. The certificate C consists of pairs of indices of x, along with a certificate. Since the certificate

is polysize, there is some r ∈ N such that the size of any index pair and its associated

certificate is O(nr). There are at most O(n2) possible substrings to choose from, and so the

overall certificate size is at most O(nr+2), and so the certificate C is also polynomial in size.

4. The important thing to see here is that we’re trying to show that, for all partitions of x into

substrings w1, . . . , wk, at least one of the wi is in L. If this is not the case, then there is at

least one partition of x into substrings such that each substring is in L. What we’ll do is try

to build such a partition, and accept iff we can be convinced that we can’t do so.

4

Now, if such a partition exists, it must have an initial string x0:j for some j. This string

cannot be in L, and so we can’t have a certificate Cx0:j for it. So we can remove from

our considerations any string x0:j that we can prove through our certificates cannot be the

first string in our partition. Once we’ve done so, there will be some (possibly empty) set of

indices that we can reach from index 0 in our partition. We’ll go to the next reachable index

down from 0 and apply the same principle – we should be able to find a next string in the

sequence. Once we’re done this process, we’ll have a list of indices we can reach from index 0

by using substrings that have not been proven to be in L. If this list contains the last possible

breakpoint n, we can build a partition that contains strings not proven to be in L3, and so

we reject. If we can’t reach index n, we know that there is no partition whose strings are all

in L3, and so we accept.

Note that our indices in questions 2 and 3 are for the breaks between letters, not for the letters

themselves. That’s why they go from 0 to n, not n− 1.

Let V ′ = “On input 〈x,C〉:

1. If x = ε, reject.

2. For (i, j) ∈ S:

3. Run V on 〈xi:j , Cxi:j 〉.

4. If it rejects, reject.

5. Make a list [0, . . . , n] of indices. Mark index 0 as reachable, and the others as unreachable.

6. Let i = 0.

7. While i < n:

8. For all j such that (i, j) /∈ S:

9. Mark j as reachable.

10. Let i be the next vertex marked as reachable. If no such vertex exists, set i = n.

11. If n is marked as reachable, reject. Else, accept.

5. Since there are at most O(n2) substrings considered, the loop from lines 2-4 runs at most

O(n2) times. If the verifier V takes nr′ time to run, this loop takes O(nr′+2) time. Creating

a list of indices in step 5. takes O(n) time. Finally, the loop from lines 7-10 runs at most n

times. each iteration takes at most O(n2) time to loop through the indices in S, and another

O(n) time to find the next reachable vertex.

So the overall time takes is O(nmax (r′+2,3)) = O(nr′+2) time (since r′ ≥ 1 if we want V to be

able to read the whole input).

So L∗ ∈ co-NP.

6. (25 marks)

Let Root-Clique =

{〈G = (V,E)〉 ∣∣G is an undirected graph with a clique of size at least √|V |}.

(a) (5 marks) Show that Root-Clique ∈ NP.

Solution:

1) This is a language, so its decision problem is a yes/no question.

2) A certificate c would be a set of nodes forming a clique of size at least

√|V |.

3) We can see that this certificate is a set of nodes in V , so |c| 6 |V |, and so this certificate

is polynomial in the size of the input.

5

4) A verifier V for this language would be:

V = “On input 〈G = {V,E}, c〉:

1. Check that every node in c is in V , and occurs no more than once.

2. Check that the |c| > k√|V |).

3. For every u ∈ C:

4. For every v 6= u ∈ C:

5. Check that uv ∈ E.

6. If all of these checks pass, accept, otherwise reject.

5) If n is the number of nodes in the graph, then:

• We can have a p that has up to n nodes, and in line 1 we will have to compare each of

these nodes to each other (and to the nodes in V ). So line 1 takes O(n2) time.

• Lines 2 checks the size of c, which takes O(n) time.

• The loops run at most O(n2) times, and in a reasonable (say, adjacency matrix) repre-

sentation, each iteration will take O(1) time. So the loop takes O(n2) time.

• Line 6 takes O(1) time.

• So altogether, the verifier takes O(n2) time.

So the verifier runs in polytime.

(b) (10 marks) Assuming that Clique is NP-complete, show that Root-Clique is NP-complete.

Solution:

We know from part a) that Root-Clique is in NP. So we just need to show that it is

NP-hard. We’ll do this with a reduction from Clique.

Let P = “On input 〈G = (V,E), k〉:

1. Let G′ = G.

2. Add |V |2 − |V | disconnected nodes to G′.

3. Take the first |V | − k of these extra nodes and add fully connect them

to form an (|V | − k)-clique.

4. Add an edge from every node in this clique to every node from the original G.

2. Return 〈G′〉.”

Proof that 〈G, k〉 ∈Clique iff 〈G′〉 ∈Root-Clique:

⇒) Suppose that G has a k-clique S.

Let S′ be the new (|V | − k)-clique added in the construction of G′.

Since every node in S′ is connected to every node from G, S∪S′ for an ((|V |−k)+k) = |V |-

clique.

Since

√|V ′| = √|V |2 = |V |, S ∪ S′ is a root-clique of G′.

So G′ ∈Root-Clique.

⇐) Suppose that G′ has a root-clique S′.

Then, since only |V | − k of the extra nodes are not disconnected, we know that at most

|V | − k of the nodes in S′ areof this type.

So at least k of the nodes in S′ nodes are in G. Let S = V ∩ S′.

Since |S| > k and S is completely connected, S is a k-clique in G.

So 〈G, k〉 ∈Clique.

Note: another natural way to do this reduction would be to break it into two cases: one

for when k <

√|V |, and one for when k > √|V |. If you’ve done that, it’s fine. Both

cases should look a little like what we’ve done above.

6

(c) (10 marks) Show how you could use an oracle MC for Root-Clique to find a certificate for it:

that is, use MC to build a polytime program that, given an instance 〈G = (V,E)〉 of Root-

Clique, will return a clique of size at least

√|V | if such a clique exists, and will return null

otherwise.

Solution:

Suppose that we had an oracle MC that could solve Root-Clique in polytime. Here is an

algorithm to find a clique of size >

√|V |:

P = “On input 〈G = {V,E}〉:

1. If |V | = 1, return V .

2. Run MC on 〈G〉.

3. If the answer if no, reject.”

4. Let G′ = G.

5. For v ∈ V :

6. Let G′′ = G′ with the edges touching v removed.

7. Run MC on 〈G′′〉.

8. If it outputs yes, set G′ = G′′.

9. Return the set of nodes in G′ that have non-zero degree.

If G has one node, then its one node is also a root-clique, so we can safely return the entire

vertex set. Otherwise, we can see that if G does not have a root-clique, P will return null. If

it does have a root-clique, it will have at least one after every loop iteration. So G′ will have

at least one root-clique when the loop terminates. If there is any node v that is not in this

root clique, the loop would have removed in in lines 7 to 9 in the loop iteration in which v

was considered. So the only connected nodes in G′ are those in the root-clique, and so the

algorithm returns a root-clique, as desired.

Suppose that MC runs in O(nk) time for some k ∈ N. Then, lines 1,3, and 4 all take O(n2)

time (remember that we can have O(n2) edges in a graph), while line 2 takes O(nk) time.

The loop runs one for every node in G, so it takes O(n) iterations. In these iterations, lines 6

and 8 take O(n2) time, and line 7 takes O(nk) time. So all told, the loop takes O(n1+max (2,k))

time, and the other lines in the program take O(nmax (2,k)) time. So the whole program takes

O(n1+max (2,k)) time. So this program is polytime.

Note: it’s OK to treat MC as taking O(1) time, as long as you state what you’re doing. If

you do, you’ll get a running time of O(n3). If you go by total input size rather than setting n

to be the number of nodes, you’ll get a slightly different number, but shouldn’t get more than

a quadratic difference from what we got here.

7. (15 marks) Let Longest-Path=

{〈G, s, t, k〉 ∣∣G is a directed graph with a path of length > k from s to t}.

(a) (5 marks) Show that Longest-Path ∈ NP.

Solution:

1) This is a language, so its decision problem is a yes/no question.

2) A certificate p for this language would be a path v1 = s, v2, . . . , v` = t from s to t of

length > k.

3) This certificate is a list of nodes in G, so its size is |p| 6 |V |. So the entire certificate is

polynomial in the size of the input.

7

4) A verifier V for this language would be:

V = “On input 〈G = {V,E}, s, t, k, c〉:

1. Check that every node in p is in V , and occurs no more than once in the path.

2. Check that the first node in p is s and that the last node is t.

3. Check that the path has > k nodes (i.e., that the length of the path is > k).

4. For vi, vi+1 ∈ p:

5. Check that vvvi+1 ∈ E.

6. If all of these checks pass, accept, otherwise reject.

5) If n is the number of nodes in the graph, then:

• We can have a p that has up to n nodes, and in line 1 we will have to compare each of

these nodes to each other (and to the nodes in V ). So line 1 takes O(n2) time.

• Lines 2 and 3 together look at each node in p a fixed number of times, so we get a time

of O(n).

• The loop runs at most n− 1 times, and in a reasonable (say, adjacency matrix) repre-

sentation, each iteration will take O(1) time. So the loop takes O(n) time.

• Line 6 takes O(1) time.

• So altogether, the verifier takes O(n2) time.

So the verifier runs in polytime.

(b) (10 marks) Assuming that HAM-PATH is NP-complete, show that Longest-Path is NP-

complete.

Solution:

We know from part a) that Longest-Path is in NP. So we just need to show that it is

NP-hard. We’ll do this with a reduction from HAM-PATH.

Let P = “On input 〈G = (V,E), s, t〉:

1. Let k′ = |V | − 1.

2. Return 〈G, s, t, k′〉.”

Proof that 〈G, s, t〉 ∈HAM-PATH iff 〈G, s, t, k′〉 ∈Longest-Path:

⇒) Suppose that G has a Hamiltonian path p from s to t.

Then, p passes through each vertex exactly once, and so it has |V | − 1 = k′ edges.

So G has a path of length k′ from s to t.

So 〈G, s, t, k′〉 ∈Longest-Path.

⇐) Suppose that G has a length-k′ path p from s to t.

Then, since p can pass through any vertex at most once, it touches k′+ 1 vertices exactly

once.

Since k′ = |V | − 1, p must hit all |V | vertices.

So p is a Hamiltonian path from s to t.

So 〈G, s, t〉 ∈HAM-PATH.

8. Bonus (10 marks — your mark will be rounded to the nearest multiple of 2.5)

Suppose you had an oracle MO that would tell you in a single step whether at least half of the truth

assignments for a boolean formula φ would return true. Use this oracle to build a polytime algorithm

that can tell, given an input boolean formula φ, exactly how many of its truth assignments are satisfying

assignments.

8

Solution:

The first thing to notice is that, given a Boolean formula F , calling MO on F will tell us if half of

more of the truth assignments to F accept, and calling MO on ¬F will tell us if half or less of the

truth assignments to F are accepting. So two calls to MO will tell us whether F is satisfied by

fewer than half of its assignments, half of its assignments, or more than half of its assignments.

We’ll argue that copying out ¬F takes linear time, so we can do the above two checks in linear

time. (*)

So, given a Boolean formula φ, we’re going to use (*) to run a binary search to find the number

of satisfying truth assignments to φ.

Suppose that we are given a Boolean formula φ with k variables. So there are 2k possible truth

assignments.

Given any i, 0 6 i < 2k, we’ll denote by ψi,k the Boolean formula on k variables that reads the k

variables as a binary number, and outputs true iff that number is less than i.

It may not be immediately clear that this is possible, but youll see it’s not too hard: e.g., if k

were 4 and i were 11, we’d want all numbers at most

10 = 10102.

It’s easy enough to build this formula: the number can start with either 0 or 1. If the number

starts with 0 (the first bit is 0) then it’s at most 8, so we accept. If it starts with 1, then the

second bit must be 0, otherwise it would be larger than 12. We can continue with this process

to get

ψ10,4 = x1 ∨ (x1 ∧ x2 ∧ (x3 ∨ (x3 ∧ x4))).

The fromula ψ0,k would always be false, e.g., (x1 ∧ x1). With this construction, we can see

that the number of truth assignments satisfying ψi,k is exactly i. We’ll argue that we can do

this construction in linear time.

Let Fi be the Boolean formula (b ∧ ψi,k) ∨ (b ∧ φ), where:

• ψi,k is as above, but which uses k new variables — there’s no overlap with the variables in φ.

• φ is our input.

• b is a single Boolean variable not used in either φ or ψi,k.

We can see that Fi will have 2k + 1 variables, and so it will have 2

2k+1 truth assignments. If

MO indicates that exactly half of its assignments are satisfying (as per (*)), then the number of

satisfying truth assignments is 22k+1/2 = 22k.

Let’s denote the number of satisfying truth assignments to φ as c. Then, the number of satisfying

truth assignments to Fi are of one of two forms:

• b = 1 and ψi,k is true, or

• b = 0 and φ is false.

• If b = 1 and ψi,k is true, there is one way b can be set (b = 1), and there are i ways that the

variables in ψi,k can be set (this is how many numbers are between 0 and i).

In this case we don’t care how the variables in φ are set, so they can take all 2k possible

values.

So there are 1× i× 2k = i2k truth assignments of this form.

• If b = 0 and φ is true, there is one way b can be set (b = 0), and there are 2k − c ways that

the variables in φ can be set.

In this case we don’t care how the variables in ψi,k are set, so they can take all 2

k possible

values.

So there are 1× (2k − c)× 2k = 22k − c2k truth assignments of this form.

9

The two types of truth assignments are disjoint — you can’t have b = 0 and b = 1 — and so the

total number of truth assignments to Fi is 2

2k + (i− c)2k. Now,

• If i < c, (i− c) < 0, and so the number of sasisfying truth assignments to Fi is less than 22k

(less than half).

• If i > c, (i− c) > 0, and so the number of sasisfying truth assignments to Fi is more than 22k

(more than half).

• If i = c, (i − c) = 0, and so the number of sasisfying truth assignments to Fi is exactly 22k

(exactly half).

So here’s our algorithm:

V = “On input φ:

1. Let Found = false; Low = 0; High = 2k.

2. While not Found:

3. Let i = b(High + Low)/2c; Fi be as described above.

4. Run MO on Fi and ¬Fi.

5. If it indicates that exactly half of the truth assignments are accepting, return i.

6. If less than half of the truth assignments are accepting, set High = i.”

7. If more than half of the truth assignments are accepting, set Low = i+ 1.”

Since this is just a binary search on the is, it will terminate in O(log (2k)) = O(k) loop iterations,

and by the arguments aboce, when it does we will know that the number of truth assignments in

φ will be exactly i.

We can see that each loop iteration will take O(n) time, where n is the size of φ. Moreover, there

are O(k) = O(n) loop iterations. So the whole process takes O(n2) time.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- 代写 Lab 2: Threads 2022-05-10
- 辅导assessment 1. Present Your Client ... 2022-05-10
- 5Cce2sas辅导、Python，Java程序辅导 2022-05-10
- 代写brae Webb编程 2022-05-09
- 辅导csci 3110 Assignment 1 2022-05-09
- Mth2222 Assignment 2代写 2022-05-09
- Cse3bdc Assignment 2022辅导 2022-05-08
- 辅导cis 468、辅导java，Python编程 2022-05-08
- Comp Sci 4094/4194/7094 Assignment 3 D... 2022-05-07
- Cs 178: Machine Learning & Data Mining... 2022-05-07
- Data7703 Assignment 4 2022-05-07
- 讲解assignment 2: Databases 2022-04-25
- 辅导ait681 Static Analysis 2022-04-25
- Cse121 & Cse121l 编程辅导、辅导c++程序语言 2022-04-25
- 辅导iti1120 Bject-Oriented Programming 2022-04-25
- Cmt304语言辅导、辅导c++，Python编程 2022-04-25
- 辅导comp/Engn4528 Computer Vision 2022-04-24
- 辅导fin 2200 Bloomberg Investment Proj... 2022-04-24
- 辅导bism 7255 Uml Assignment 2022-04-23
- 讲解comp202 Programming Assignment 2022-04-23