Yioop - PHP Search Engine

Practice Midterm 2 is up.

Hey Everyone,

Practice Midterm 2 is up.

Best,
Chris

Hey Everyone, Practice Midterm 2 is up. Best, Chris

-- Practice Midtern #2 Answers [Problem 3]

Originally Posted By: asingh

Use closure properties of NP and the space hierarchy theorem to show that SPACE(n)≠NP.

Argument:

1. Let's suppose, NP = SPACE(n)

2. Then we can reduce any PSPACE(n) problem to SPACE(n) (linear space) problem in polynomial time.
Well, this can be achieved by padding to linear space problem.

3. So, PSPACE(n) = SPACE(n)

4. But by the space hierarchy theorem, PSPACE(n) != SPACE(n)

5. So, that contradicts our supposition about NP = SPACE(n).

Cheers!

'''Originally Posted By: asingh''' Use closure properties of NP and the space hierarchy theorem to show that SPACE(n)≠NP. Argument: 1. Let's suppose, NP = SPACE(n) 2. Then we can reduce any PSPACE(n) problem to SPACE(n) (linear space) problem in polynomial time. Well, this can be achieved by padding to linear space problem. 3. So, PSPACE(n) = SPACE(n) 4. But by the space hierarchy theorem, PSPACE(n) != SPACE(n) 5. So, that contradicts our supposition about NP = SPACE(n). Cheers!

-- Practice Midtern #2 Answers [Problem 2]

Originally Posted By: stang

Midterm #2 Question #2:
State and prove the nondeterministic time hierarchy theory.

Theorem: If f, g are time constructible functions that satisfying f(n + 1) = o(g(n)), then
NTIME(f(n)) is strictly contained in NTIME(g(n))

Fortnow and Santhanam (2010) Proof:
Let M_1,... be an enumeration of nondeterministic Turing machines. We define a nondeterministic machine M that acts as follows on input w = 1^i 01^m 0y:
•If |y| then accept if M_i accepts both inputs 1^i 01^m 0y0 and 1^i 01^m 0y1 in g(|w|) steps.
•If |y|=f(I + m + 2) then accept if M_i rejects input 1^i 01^m 0 on the computation path described by y in g(|w|) steps.

This machine uses time O(g(n)). If NTIME(f(n))=NTIME(g(n)) then there is an equivalent machine M_i using time O(f(n)). Since f(n + 1) = o(g(n)) we have for sufficiently large m,
1^i 01^m 0 ∈ L(M) ⇔ 1^i 01^m 0y ∈ L(M) for |y| = 1 ⇔ ...
⇔ 1^i 01^m 01y ∈ L(M) for |y| = f(i + m + 2) ⇔ M(1^i 01^m 0) rejects on all computation paths y a contradiction.

Zak (Textbook) Proof:
Assume there is a function f: N → N and f(1) = 2 and f(i + 1) = 2^f(i)^1.2. Given a diagonalizing machine D with the following properties:

On input x, if x ∉ 1*, reject. If x = 1^n, then compute i such that f(i) and
1.If f(i) then simulate M_i on input 1^n + 1 using nondeterminism in n^1.1 time and output its answer. (If M_i has not halted this time, then halt and accept.)
2.If n = f(i + 1) then accept 1^n iff M_i rejects 1^f(i) + 1 in (f(i) + 1)^1.1 time.

Please also note that D will try to flip the answer of M_i on some input in the set {1^n: f(i) . Also, the #2 requires going through all possible 2^(f(i) + 1)^1.1 branches of M_i on input 1^f(i) + 1, but that is acceptable since the input size f(i + 1) is 2^f(i) ^1.2. Hence the NDTM D runs in O(n^1.5) time.

If L is the language decided by D, then L ∉ NTIME(n). For contradiction sake, if L is decided by an NDTM M running in cn step for some constant c, we can find i large enough such that M = M_i and on output of length n ≥ f(i), M_i can be simulated in less than n^1.1 steps. As such, the 2 steps in D ensure that
-If f(i) then D(1^n) = M_i(1^n + 1), whereas D(1^f(n + 1)) ≠ M_i(1^f(n + 1))

By assumption, M_i and D will agree on all inputs 1^n for n in the semi-open interval (f(i), f(i + 1)). This implies that D(1^f(n + 1)) = M_i(1^f(n + 1)) but contradicting with the 2 steps in D.

'''Originally Posted By: stang''' Midterm #2 Question #2: State and prove the nondeterministic time hierarchy theory. Theorem: If f, g are time constructible functions that satisfying f(n + 1) = o(g(n)), then NTIME(f(n)) is strictly contained in NTIME(g(n)) Fortnow and Santhanam (2010) Proof: Let M_1,... be an enumeration of nondeterministic Turing machines. We define a nondeterministic machine M that acts as follows on input w = 1^i 01^m 0y: •If |y| then accept if M_i accepts both inputs 1^i 01^m 0y0 and 1^i 01^m 0y1 in g(|w|) steps. •If |y|=f(I + m + 2) then accept if M_i rejects input 1^i 01^m 0 on the computation path described by y in g(|w|) steps. This machine uses time O(g(n)). If NTIME(f(n))=NTIME(g(n)) then there is an equivalent machine M_i using time O(f(n)). Since f(n + 1) = o(g(n)) we have for sufficiently large m, 1^i 01^m 0 ∈ L(M) ⇔ 1^i 01^m 0y ∈ L(M) for |y| = 1 ⇔ ... ⇔ 1^i 01^m 01y ∈ L(M) for |y| = f(i + m + 2) ⇔ M(1^i 01^m 0) rejects on all computation paths y a contradiction. Zak (Textbook) Proof: Assume there is a function f: N → N and f(1) = 2 and f(i + 1) = 2^f(i)^1.2. Given a diagonalizing machine D with the following properties: On input x, if x ∉ 1*, reject. If x = 1^n, then compute i such that f(i) and 1.If f(i) then simulate M_i on input 1^n + 1 using nondeterminism in n^1.1 time and output its answer. (If M_i has not halted this time, then halt and accept.) 2.If n = f(i + 1) then accept 1^n iff M_i rejects 1^f(i) + 1 in (f(i) + 1)^1.1 time. Please also note that D will try to flip the answer of M_i on some input in the set {1^n: f(i) . Also, the #2 requires going through all possible 2^(f(i) + 1)^1.1 branches of M_i on input 1^f(i) + 1, but that is acceptable since the input size f(i + 1) is 2^f(i) ^1.2. Hence the NDTM D runs in O(n^1.5) time. If L is the language decided by D, then L ∉ NTIME(n). For contradiction sake, if L is decided by an NDTM M running in cn step for some constant c, we can find i large enough such that M = M_i and on output of length n ≥ f(i), M_i can be simulated in less than n^1.1 steps. As such, the 2 steps in D ensure that -If f(i) then D(1^n) = M_i(1^n + 1), whereas D(1^f(n + 1)) ≠ M_i(1^f(n + 1)) By assumption, M_i and D will agree on all inputs 1^n for n in the semi-open interval (f(i), f(i + 1)). This implies that D(1^f(n + 1)) = M_i(1^f(n + 1)) but contradicting with the 2 steps in D.

-- Practice Midtern #2 Answers

Originally Posted By: jnewth

Could everyone please post the rest of the answers?

'''Originally Posted By: jnewth''' Could everyone please post the rest of the answers?

Practice Midterm #2 Answers

Originally Posted By: jnewth

Problem 5. State and prove Savitch's Theorem.

This proof is in the book on page 86. The professor's proof of Savitch's Theorem is presented as an example using PATH in October 19th's notes. I will explain the book's proof.

The theorem is stated as:

For any space constructible function S: N->N with S(n) >= log n, NSPACE(S(n)) is contained in SPACE(S(n)^2)

For a language L in NSPACE(S(n)) there is a Turing Machine called TM running on an input x of length that decides that language in space S(n). The configuration graph G for such a machine takes at most M = 2^O(S(n)) vertices, and determining whether TM accepts x is the same as finding a path from Cstart to Caccept. This is because all possible values for a binary string of length n is 2^n. The state of the machine at any time is one of those strings.

The proof involves describing a way of finding that path deterministically in S(n)^2. The longest any path can be is one that passes through all nodes, so we describe the maximum possible length as 2^i. The proof describes a function Reach(u,v,i), which returns true iff there is a path from u, v, in at most 2^i steps. We then solve this problem recursively, observing

Reach(u,v,i) = Reach(u,z,i-1) and Reach(z,v,i-1)

by iterating over all possible nodes for z. Please note, Reach(u,z,i-1) means a path from u to z in 2^i-1 steps or rather 2^i / 2 steps.

We can reuse the space to compute each invocation of Reach, but at each recursive call, we need to keep track of the z we are currently splitting the search on, and to identify any particular node in the graph G requires log(M) space. We can divide the search space by two a total of log(M) times, so we need to keep track of log(M) space for each of log(M) divisions or log(M)*log(M).

For the final part, we observe that log(M) = log(2^O(S(n)) = S(n), so

log(M)*log(M) = S(n)^2

which is the statement of Savitch's Theorem.

'''Originally Posted By: jnewth''' Problem 5. State and prove Savitch's Theorem. This proof is in the book on page 86. The professor's proof of Savitch's Theorem is presented as an example using PATH in October 19th's notes. I will explain the book's proof. The theorem is stated as: For any space constructible function S: N->N with S(n) >= log n, NSPACE(S(n)) is contained in SPACE(S(n)^2) For a language L in NSPACE(S(n)) there is a Turing Machine called TM running on an input x of length that decides that language in space S(n). The configuration graph G for such a machine takes at most M = 2^O(S(n)) vertices, and determining whether TM accepts x is the same as finding a path from Cstart to Caccept. This is because all possible values for a binary string of length n is 2^n. The state of the machine at any time is one of those strings. The proof involves describing a way of finding that path deterministically in S(n)^2. The longest any path can be is one that passes through all nodes, so we describe the maximum possible length as 2^i. The proof describes a function Reach(u,v,i), which returns true iff there is a path from u, v, in at most 2^i steps. We then solve this problem recursively, observing Reach(u,v,i) = Reach(u,z,i-1) and Reach(z,v,i-1) by iterating over all possible nodes for z. Please note, Reach(u,z,i-1) means a path from u to z in 2^i-1 steps or rather 2^i / 2 steps. We can reuse the space to compute each invocation of Reach, but at each recursive call, we need to keep track of the z we are currently splitting the search on, and to identify any particular node in the graph G requires log(M) space. We can divide the search space by two a total of log(M) times, so we need to keep track of log(M) space for each of log(M) divisions or log(M)*log(M). For the final part, we observe that log(M) = log(2^O(S(n)) = S(n), so log(M)*log(M) = S(n)^2 which is the statement of Savitch's Theorem.

-- Practice Midterm #2 Answers

Originally Posted By: jnewth

Problem 6. Prove PATH is in NL.

This is shown on page 82 of the book and in the notes of October 19th. Savitch's Theorem is stated as a corollary of this result.

PATH = { : G is a directed graph in which there is a path from s to t }

Note the longest path in a given graph between any two nodes is a path that goes through every other node. If there is are n nodes in G, then the longest path is n steps.

We show PATH is in NL by describing the operation of the nondeterministic machine M deciding PATH. M given an instance of the problem x = could find a path from s to t by repeatedly seeing which node it is currently on and then nondeterministically deciding which node to go to next. If it keeps count of how many steps it has taken. If it ever takes more than n steps and hasn't arrived at t, it rejects. The question discussed in class "what if it gets stuck in a loop?" is answered with the simple idea that a nondeterministic machine given a choice between a path to a and a path to b can be thought of as either "making the right choice" or perhaps more accurately "making both choices simultaneously".

We can easily see that to keep track which node we are currently on in a graph of size n requires log(n) space. To keep track of how many steps we have taken out of n possible steps also takes log(n) space. Therefore our nondeterministic machine operates in O(log n) space, as desired.

'''Originally Posted By: jnewth''' Problem 6. Prove PATH is in NL. This is shown on page 82 of the book and in the notes of October 19th. Savitch's Theorem is stated as a corollary of this result. PATH = { : G is a directed graph in which there is a path from s to t } Note the longest path in a given graph between any two nodes is a path that goes through every other node. If there is are n nodes in G, then the longest path is n steps. We show PATH is in NL by describing the operation of the nondeterministic machine M deciding PATH. M given an instance of the problem x = could find a path from s to t by repeatedly seeing which node it is currently on and then nondeterministically deciding which node to go to next. If it keeps count of how many steps it has taken. If it ever takes more than n steps and hasn't arrived at t, it rejects. The question discussed in class "what if it gets stuck in a loop?" is answered with the simple idea that a nondeterministic machine given a choice between a path to a and a path to b can be thought of as either "making the right choice" or perhaps more accurately "making both choices simultaneously". We can easily see that to keep track which node we are currently on in a graph of size n requires log(n) space. To keep track of how many steps we have taken out of n possible steps also takes log(n) space. Therefore our nondeterministic machine operates in O(log n) space, as desired.

-- Practice Midterm #2 Answers

Originally Posted By: nkeerthy

9th Solution:

TISP(n^14,n^2)⊆Σ2 TIME(n^9).

Suppose that L is decided by a machine M using n^14 times and n^2 space. For every x∈{0,1}⋆, consider the configuration G M,x of M on input x. Each configuration in this graph can be described by a string of length O(n^2) and x is in L iff then is a path of length n^14 in this graph starting at Cstart to an accepting configuration. There is such a path iff there exists n^7 configurations C1...Cn^7 such that if we let C0=Cstart then Cn6 is accepting and for every i∈[n7] the configuration Ci is computed from Ci-1 within n^7 steps. This later condition can be verified in O(n^8) time, giving an O(n^8)-time Σ2-TM for deciding membership in L.

10th Solution:

Prove NP SAT=Σ 2 p.

Theorem present in professors slides from Oct 31, slide 6
PH via Oracle Machines

'''Originally Posted By: nkeerthy''' 9th Solution: TISP(n^14,n^2)&sube;Σ2 TIME(n^9). Suppose that L is decided by a machine M using n^14 times and n^2 space. For every x∈{0,1}⋆, consider the configuration G M,x of M on input x. Each configuration in this graph can be described by a string of length O(n^2) and x is in L iff then is a path of length n^14 in this graph starting at Cstart to an accepting configuration. There is such a path iff there exists n^7 configurations C1...Cn^7 such that if we let C0=Cstart then Cn6 is accepting and for every i∈[n7] the configuration Ci is computed from Ci-1 within n^7 steps. This later condition can be verified in O(n^8) time, giving an O(n^8)-time Σ2-TM for deciding membership in L. 10th Solution: Prove NP SAT=Σ 2 p. Theorem present in professors slides from Oct 31, slide 6 PH via Oracle Machines