2011-09-28
Please post your practice midterm solutions to this thread.
Please post your practice midterm solutions to this thread
Please post your practice midterm solutions to this thread
2011-09-30
Originally Posted By: jnewth
Problem 7. Briefly explain how the amortized shifting works in our O(TLogT) universal TM simulation.
The amortized shifting is presented in the notes of September 12. It is presented as an improvement over the T^2 universal TM presented on pg 20-21 of the book. The T^2 UTM is summarized here:
Given a 3-tape (input, output, work) TM M, we can simulate each step of this machine using our 5-tape UTM. One of the extra UTM work tapes stores some representation of M's transition function and the other extra work tape acts as a register to store the current state of M. Thus, to simulate one step of M, we read the current state of M from the worktape, we scan the transition function on the other worktape, then update M's worktape and output tape as required. Each step of M takes C steps of UTM (the steps taken to scan the transition function are constant and the steps taken to update the register worktape are constant). But wait! It appears that if the runtime of M is T, then the runtime of UTM is C*T! The thing to remember is that the original TM may have been some other type of TM that was transformed in to the familiar 3-tape representation. This transformation may have introduced a quadratic slowdown, so we bound the UTM's operation with C'T^2.
The motivation for the amortizing shifting UTM is as follows. We can imagine a k-tape TM that we wish to simulate using our UTM. We can do this by expanding the alphabet of our UTM such that for each unique set of squares over the k-tapes we have a unique symbol in our UTM alphabet (pg 29). When you think about it, representing these 5 tapes as 5 tapes or as 1 tape are equivalent - it's just where you write the symbols. The problem is that in the k-tape machine we can assume k heads as well! But because it's easier to think of the tapes as separate, think of them as separate tapes that are all connected. Now, we can still move our k-tapes, but they have to move all together because they are connected. To simulate the independent motion of each tape, we will define a shift operation. This is pretty easy to describe. Let's pretend that we are going to move tape 1 to the right by 1 square with respect to the rest of the tapes. We would just have to index over all the squares of tape 1 from right to left, at each square writing each symbol to the next rightmost position. This would then make the symbols on the tape appear to have moved by 1 square with respect to the rest of the tapes, right?
The important thing is that we can still shift each tape's symbols with respect to the tape by this shift operation (shift as repeated copying and pasting). If you do the analysis, this still runs in O(T^2), because for each time we want to move a single square, we might have to move the whole string of symbols! The idea then is to write our sequence of symbols on each tape in such a way that when we have to move a single square, we can only bump a few symbols over, rather than the entire string of symbols.
The zones achieve this. By writing our symbols in zones, we leave spaces (which are not "blank" - the book uses squares with x's in them) so that we can shift symbols in to those spaces as needed.
Let's not worry about the analysis right now. Let's just make sure we understand how the shift operation would work. Please turn to page 31 of the book for the picture.
Following the steps of "Performing a shift":
1. We identify the smallest io such that Rio is NOT empty (meaning it's either full or half full). In our case, we are performing a left shift of tape 1, so that means R2 is the first first non-empty zone (because it contains "ly"). We shift "l" to position 0, and then we go to step 2. Because R2 is the highest non empty zone, this shift operation has INDEX=2.
2. Shift the rest of the lower half of zone R2 in to R0 and R1. This is possible because R2 = 8 squares. R1 = 4 squares, and R0 = 2 squares. If R2 was completely full, that means we need to relocate the top half of R2 in to the bottom half of R2, and then put the bottom half of R2 in to R1 and R0, without violating our "empty, half or completely full" rule for the zones. We take the four bottom squares of R2, put one square in to position 0, one in to the bottom half of zone 1, and two in to the bottom half of R1.
3. We then have to do the same shift operation on the left side of the tape, but again enforcing the notion that you only consume half the squares of a zone.
So now this looks like a lot of work to just move one square. Have we gained anything? Well, yes. Now that we moved something involving index 2, the next 2^i - 1 shifts will only use the zones 0 and 1, which obviously take a lot less work (I think half as much).
The analysis is a bit involved, but essentially:
Each zone represents 2^(i+1) squares.
To shift a zone of index i is proportional to the total size of the zones. The summation in the notes says sum from 0 to i for 2*2^i. In our case we calculate
number of shifts ~ 2*(2^0 + 2^1+ 2^2) = 14. This works out. For R2, we have to shift 4 elements. For R1 we have to shift 2. For R0 we just shift 1. And then we have to do the left side. I think we might be missing a constant in here, but that's going to drop out anyhow. So our shift operation is O(2^i) operations.
The final summation over k tapes for our worst case index and worst case number of shifts is on page 32 as O(T log T).
The amortized shifting is presented in the notes of September 12. It is presented as an improvement over the T^2 universal TM presented on pg 20-21 of the book. The T^2 UTM is summarized here:
Given a 3-tape (input, output, work) TM M, we can simulate each step of this machine using our 5-tape UTM. One of the extra UTM work tapes stores some representation of M's transition function and the other extra work tape acts as a register to store the current state of M. Thus, to simulate one step of M, we read the current state of M from the worktape, we scan the transition function on the other worktape, then update M's worktape and output tape as required. Each step of M takes C steps of UTM (the steps taken to scan the transition function are constant and the steps taken to update the register worktape are constant). But wait! It appears that if the runtime of M is T, then the runtime of UTM is C*T! The thing to remember is that the original TM may have been some other type of TM that was transformed in to the familiar 3-tape representation. This transformation may have introduced a quadratic slowdown, so we bound the UTM's operation with C'T^2.
The motivation for the amortizing shifting UTM is as follows. We can imagine a k-tape TM that we wish to simulate using our UTM. We can do this by expanding the alphabet of our UTM such that for each unique set of squares over the k-tapes we have a unique symbol in our UTM alphabet (pg 29). When you think about it, representing these 5 tapes as 5 tapes or as 1 tape are equivalent - it's just where you write the symbols. The problem is that in the k-tape machine we can assume k heads as well! But because it's easier to think of the tapes as separate, think of them as separate tapes that are all connected. Now, we can still move our k-tapes, but they have to move all together because they are connected. To simulate the independent motion of each tape, we will define a shift operation. This is pretty easy to describe. Let's pretend that we are going to move tape 1 to the right by 1 square with respect to the rest of the tapes. We would just have to index over all the squares of tape 1 from right to left, at each square writing each symbol to the next rightmost position. This would then make the symbols on the tape appear to have moved by 1 square with respect to the rest of the tapes, right?
The important thing is that we can still shift each tape's symbols with respect to the tape by this shift operation (shift as repeated copying and pasting). If you do the analysis, this still runs in O(T^2), because for each time we want to move a single square, we might have to move the whole string of symbols! The idea then is to write our sequence of symbols on each tape in such a way that when we have to move a single square, we can only bump a few symbols over, rather than the entire string of symbols.
The zones achieve this. By writing our symbols in zones, we leave spaces (which are not "blank" - the book uses squares with x's in them) so that we can shift symbols in to those spaces as needed.
Let's not worry about the analysis right now. Let's just make sure we understand how the shift operation would work. Please turn to page 31 of the book for the picture.
Following the steps of "Performing a shift":
1. We identify the smallest io such that Rio is NOT empty (meaning it's either full or half full). In our case, we are performing a left shift of tape 1, so that means R2 is the first first non-empty zone (because it contains "ly"). We shift "l" to position 0, and then we go to step 2. Because R2 is the highest non empty zone, this shift operation has INDEX=2.
2. Shift the rest of the lower half of zone R2 in to R0 and R1. This is possible because R2 = 8 squares. R1 = 4 squares, and R0 = 2 squares. If R2 was completely full, that means we need to relocate the top half of R2 in to the bottom half of R2, and then put the bottom half of R2 in to R1 and R0, without violating our "empty, half or completely full" rule for the zones. We take the four bottom squares of R2, put one square in to position 0, one in to the bottom half of zone 1, and two in to the bottom half of R1.
3. We then have to do the same shift operation on the left side of the tape, but again enforcing the notion that you only consume half the squares of a zone.
So now this looks like a lot of work to just move one square. Have we gained anything? Well, yes. Now that we moved something involving index 2, the next 2^i - 1 shifts will only use the zones 0 and 1, which obviously take a lot less work (I think half as much).
The analysis is a bit involved, but essentially:
Each zone represents 2^(i+1) squares.
To shift a zone of index i is proportional to the total size of the zones. The summation in the notes says sum from 0 to i for 2*2^i. In our case we calculate
number of shifts ~ 2*(2^0 + 2^1+ 2^2) = 14. This works out. For R2, we have to shift 4 elements. For R1 we have to shift 2. For R0 we just shift 1. And then we have to do the left side. I think we might be missing a constant in here, but that's going to drop out anyhow. So our shift operation is O(2^i) operations.
The final summation over k tapes for our worst case index and worst case number of shifts is on page 32 as O(T log T).
'''Originally Posted By: jnewth'''
Problem 7. Briefly explain how the amortized shifting works in our O(TLogT) universal TM simulation.<br><br>The amortized shifting is presented in the notes of September 12. It is presented as an improvement over the T^2 universal TM presented on pg 20-21 of the book. The T^2 UTM is summarized here:<br><br>Given a 3-tape (input, output, work) TM M, we can simulate each step of this machine using our 5-tape UTM. One of the extra UTM work tapes stores some representation of M's transition function and the other extra work tape acts as a register to store the current state of M. Thus, to simulate one step of M, we read the current state of M from the worktape, we scan the transition function on the other worktape, then update M's worktape and output tape as required. Each step of M takes C steps of UTM (the steps taken to scan the transition function are constant and the steps taken to update the register worktape are constant). But wait! It appears that if the runtime of M is T, then the runtime of UTM is C*T! The thing to remember is that the original TM may have been some other type of TM that was transformed in to the familiar 3-tape representation. This transformation may have introduced a quadratic slowdown, so we bound the UTM's operation with C'T^2.<br><br>The motivation for the amortizing shifting UTM is as follows. We can imagine a k-tape TM that we wish to simulate using our UTM. We can do this by expanding the alphabet of our UTM such that for each unique set of squares over the k-tapes we have a unique symbol in our UTM alphabet (pg 29). When you think about it, representing these 5 tapes as 5 tapes or as 1 tape are equivalent - it's just where you write the symbols. The problem is that in the k-tape machine we can assume k heads as well! But because it's easier to think of the tapes as separate, think of them as separate tapes that are all connected. Now, we can still move our k-tapes, but they have to move all together because they are connected. To simulate the independent motion of each tape, we will define a shift operation. This is pretty easy to describe. Let's pretend that we are going to move tape 1 to the right by 1 square with respect to the rest of the tapes. We would just have to index over all the squares of tape 1 from right to left, at each square writing each symbol to the next rightmost position. This would then make the symbols on the tape appear to have moved by 1 square with respect to the rest of the tapes, right?<br><br>The important thing is that we can still shift each tape's symbols with respect to the tape by this shift operation (shift as repeated copying and pasting). If you do the analysis, this still runs in O(T^2), because for each time we want to move a single square, we might have to move the whole string of symbols! The idea then is to write our sequence of symbols on each tape in such a way that when we have to move a single square, we can only bump a few symbols over, rather than the entire string of symbols.<br><br>The zones achieve this. By writing our symbols in zones, we leave spaces (which are not "blank" - the book uses squares with x's in them) so that we can shift symbols in to those spaces as needed.<br><br>Let's not worry about the analysis right now. Let's just make sure we understand how the shift operation would work. Please turn to page 31 of the book for the picture.<br><br>Following the steps of "Performing a shift":<br><br>1. We identify the smallest io such that Rio is NOT empty (meaning it's either full or half full). In our case, we are performing a left shift of tape 1, so that means R2 is the first first non-empty zone (because it contains "ly"). We shift "l" to position 0, and then we go to step 2. Because R2 is the highest non empty zone, this shift operation has INDEX=2.<br><br>2. Shift the rest of the lower half of zone R2 in to R0 and R1. This is possible because R2 = 8 squares. R1 = 4 squares, and R0 = 2 squares. If R2 was completely full, that means we need to relocate the top half of R2 in to the bottom half of R2, and then put the bottom half of R2 in to R1 and R0, without violating our "empty, half or completely full" rule for the zones. We take the four bottom squares of R2, put one square in to position 0, one in to the bottom half of zone 1, and two in to the bottom half of R1.<br><br>3. We then have to do the same shift operation on the left side of the tape, but again enforcing the notion that you only consume half the squares of a zone.<br><br>So now this looks like a lot of work to just move one square. Have we gained anything? Well, yes. Now that we moved something involving index 2, the next 2^i - 1 shifts will only use the zones 0 and 1, which obviously take a lot less work (I think half as much).<br><br>The analysis is a bit involved, but essentially:<br><br>Each zone represents 2^(i+1) squares. <br>To shift a zone of index i is proportional to the total size of the zones. The summation in the notes says sum from 0 to i for 2*2^i. In our case we calculate<br><br>number of shifts ~ 2*(2^0 + 2^1+ 2^2) = 14. This works out. For R2, we have to shift 4 elements. For R1 we have to shift 2. For R0 we just shift 1. And then we have to do the left side. I think we might be missing a constant in here, but that's going to drop out anyhow. So our shift operation is O(2^i) operations.<br><br>The final summation over k tapes for our worst case index and worst case number of shifts is on page 32 as O(T log T).
Originally Posted By: sctice
Problem 5: Prove the complement of HALT is undecidable.
Suppose for the sake of contradiction that the complement of HALT were decidable, and that we have a TM M that, when given a representation of a TM N and an input x, outputs 1 if N does not halt, and 0 otherwise. We can use M to reduce HALT to its complement, contradicting the theorem that HALT is undecidable. The TM M' accepts a representation of a TM N and an input x, and runs M on , then outputs 1 if M outputs 0 (meaning that N halts), and 0 if M outputs 1. If M outputs the complement of HALT(N, x) in a finite number of steps, then M' outputs HALT(N, x).
Suppose for the sake of contradiction that the complement of HALT were decidable, and that we have a TM M that, when given a representation of a TM N and an input x, outputs 1 if N does not halt, and 0 otherwise. We can use M to reduce HALT to its complement, contradicting the theorem that HALT is undecidable. The TM M' accepts a representation of a TM N and an input x, and runs M on , then outputs 1 if M outputs 0 (meaning that N halts), and 0 if M outputs 1. If M outputs the complement of HALT(N, x) in a finite number of steps, then M' outputs HALT(N, x).
'''Originally Posted By: sctice'''
Problem 5: Prove the complement of HALT is undecidable.<br><br>Suppose for the sake of contradiction that the complement of HALT were decidable, and that we have a TM M that, when given a representation of a TM N and an input x, outputs 1 if N does not halt, and 0 otherwise. We can use M to reduce HALT to its complement, contradicting the theorem that HALT is undecidable. The TM M' accepts a representation of a TM N and an input x, and runs M on , then outputs 1 if M outputs 0 (meaning that N halts), and 0 if M outputs 1. If M outputs the complement of HALT(N, x) in a finite number of steps, then M' outputs HALT(N, x).
2011-10-01
Originally Posted By: Jay_Reynolds_Freeman
3) Show carefully that n**3 is time constructible.
The general idea is this:
1) First we count the characters in the input string; that is we construct the binary representation of the length of the input string, n.
2) Then we multiply n times itself, to get n**2, using the binary representation and the algorithm developed in the posted problem solution set for Assignment 1.
3) Then we multiply n**2 times n, to get n**3.
We use a four-tape machine, with tapes INPUT, SCRATCH0, SCRATCH1 and OUTPUT. We initialize the last three with "0".
We perform (1) by walking the length of the string in INPUT: Every time we see a character there, we add "1" to the content of SCRATCH0, overwriting SCRATCH0 as we go, using conventional add-with-carry arithmetic, with the head of SCRATCH0 starting at the LSB of SCRATCH0. The only actual adds we do are to the LSB of SCRATCH0; all else is carry-propagation; it clearly takes one step per bit written. The ultimate result in SCRATCH0 will be the binary representation of n, whose length will be the ceiling of log(n). FOR BREVITY, I OMIT THE "CEILING" HEREAFTER, but it is implicit in any use of "log" herein. There are n additions to be done, so this step will take at most n*log(n) steps to do the adds and another n*log(n) steps to move the head of SCRATCH0 back to where we started.
We then we multiply SCRATCH0 by itself using shift-adds, using SCRATCH1 as the destination, in the manner described in problem 1 of the posted solution set to assignment 1. There are log(n) shift-adds to be done, and each takes no more than 2log(n) steps (since that is the length of n**2), so the whole process takes about 2[log(n)]**2 steps.
Finally we multiply SCRATCH0 by SCRATCH1 similarly, using OUTPUT as the (final) destination. There are still log(n) shift-adds to be done, but we have at most 3log(n) steps since we are calculating n**3, and the whole process takes about 3[log(n)]**2 steps.
At this point we can use the fact that log(n) = 1, and can accordingly find that the total time for the algorithm does not exceed about 6 n**2. That will be strictly less than n**3 for n > 6, and we can special case n in [2..6]: As we are scanning the input the first time, if the input ends with the character count in this range, we just write out a precalculated output. We CANNOT, however, deal with the case n = 0 or n = 1: There is no way to write "0" to the output in zero steps, and if the input length is one, we will not find out about it until we have stepped past it, and at that point we will have used up two steps already, so even if we have initialized the output tape to "1" as we stepped, we still cannot get done in one step.
The general idea is this:
1) First we count the characters in the input string; that is we construct the binary representation of the length of the input string, n.
2) Then we multiply n times itself, to get n**2, using the binary representation and the algorithm developed in the posted problem solution set for Assignment 1.
3) Then we multiply n**2 times n, to get n**3.
We use a four-tape machine, with tapes INPUT, SCRATCH0, SCRATCH1 and OUTPUT. We initialize the last three with "0".
We perform (1) by walking the length of the string in INPUT: Every time we see a character there, we add "1" to the content of SCRATCH0, overwriting SCRATCH0 as we go, using conventional add-with-carry arithmetic, with the head of SCRATCH0 starting at the LSB of SCRATCH0. The only actual adds we do are to the LSB of SCRATCH0; all else is carry-propagation; it clearly takes one step per bit written. The ultimate result in SCRATCH0 will be the binary representation of n, whose length will be the ceiling of log(n). FOR BREVITY, I OMIT THE "CEILING" HEREAFTER, but it is implicit in any use of "log" herein. There are n additions to be done, so this step will take at most n*log(n) steps to do the adds and another n*log(n) steps to move the head of SCRATCH0 back to where we started.
We then we multiply SCRATCH0 by itself using shift-adds, using SCRATCH1 as the destination, in the manner described in problem 1 of the posted solution set to assignment 1. There are log(n) shift-adds to be done, and each takes no more than 2log(n) steps (since that is the length of n**2), so the whole process takes about 2[log(n)]**2 steps.
Finally we multiply SCRATCH0 by SCRATCH1 similarly, using OUTPUT as the (final) destination. There are still log(n) shift-adds to be done, but we have at most 3log(n) steps since we are calculating n**3, and the whole process takes about 3[log(n)]**2 steps.
At this point we can use the fact that log(n) = 1, and can accordingly find that the total time for the algorithm does not exceed about 6 n**2. That will be strictly less than n**3 for n > 6, and we can special case n in [2..6]: As we are scanning the input the first time, if the input ends with the character count in this range, we just write out a precalculated output. We CANNOT, however, deal with the case n = 0 or n = 1: There is no way to write "0" to the output in zero steps, and if the input length is one, we will not find out about it until we have stepped past it, and at that point we will have used up two steps already, so even if we have initialized the output tape to "1" as we stepped, we still cannot get done in one step.
'''Originally Posted By: Jay_Reynolds_Freeman'''
3) Show carefully that n**3 is time constructible.<br><br>The general idea is this:<br><br>1) First we count the characters in the input string; that is we construct the binary representation of the length of the input string, n.<br><br>2) Then we multiply n times itself, to get n**2, using the binary representation and the algorithm developed in the posted problem solution set for Assignment 1.<br><br>3) Then we multiply n**2 times n, to get n**3.<br><br>We use a four-tape machine, with tapes INPUT, SCRATCH0, SCRATCH1 and OUTPUT. We initialize the last three with "0".<br><br>We perform (1) by walking the length of the string in INPUT: Every time we see a character there, we add "1" to the content of SCRATCH0, overwriting SCRATCH0 as we go, using conventional add-with-carry arithmetic, with the head of SCRATCH0 starting at the LSB of SCRATCH0. The only actual adds we do are to the LSB of SCRATCH0; all else is carry-propagation; it clearly takes one step per bit written. The ultimate result in SCRATCH0 will be the binary representation of n, whose length will be the ceiling of log(n). FOR BREVITY, I OMIT THE "CEILING" HEREAFTER, but it is implicit in any use of "log" herein. There are n additions to be done, so this step will take at most n*log(n) steps to do the adds and another n*log(n) steps to move the head of SCRATCH0 back to where we started.<br><br>We then we multiply SCRATCH0 by itself using shift-adds, using SCRATCH1 as the destination, in the manner described in problem 1 of the posted solution set to assignment 1. There are log(n) shift-adds to be done, and each takes no more than 2log(n) steps (since that is the length of n**2), so the whole process takes about 2[log(n)]**2 steps.<br><br>Finally we multiply SCRATCH0 by SCRATCH1 similarly, using OUTPUT as the (final) destination. There are still log(n) shift-adds to be done, but we have at most 3log(n) steps since we are calculating n**3, and the whole process takes about 3[log(n)]**2 steps.<br><br>At this point we can use the fact that log(n) = 1, and can accordingly find that the total time for the algorithm does not exceed about 6 n**2. That will be strictly less than n**3 for n > 6, and we can special case n in [2..6]: As we are scanning the input the first time, if the input ends with the character count in this range, we just write out a precalculated output. We CANNOT, however, deal with the case n = 0 or n = 1: There is no way to write "0" to the output in zero steps, and if the input length is one, we will not find out about it until we have stepped past it, and at that point we will have used up two steps already, so even if we have initialized the output tape to "1" as we stepped, we still cannot get done in one step.
Originally Posted By: stang
Q2:
Give a TM algorithm for computing palindrome.
Answer:
Let PAL be a Boolean function which for every x ∈ {0, 1} ⋆, PAL(x) is equal to 1 if x is a palindrome and PAL(x) is equal to 0 if otherwise. That is, PAL(x) = 1 if and only if x1x2...xn = xnxn-1...x1. Assuming that there is a TM M that can compute PAL within less than 3n steps, and this TM M uses 3 tapes (input, work and output) and the alphabet { Δ , □ , 0, 1}, with the following algorithm:
-Copy the input to the read-write work tape
-Move the input-tape head to the beginning of the input
-Move the input-tape head to the right while moving the work-tape head to the left. At any moment if the value from the input-tape is not the same as the value from the work-tape, the machine will halts and output 0 to the output-tape
-If the machine observes the end symbol from the input-tape or the start symbol from the work-tape, the machine will halts and output 1 to the output-tape
Give a TM algorithm for computing palindrome.
Answer:
Let PAL be a Boolean function which for every x ∈ {0, 1} ⋆, PAL(x) is equal to 1 if x is a palindrome and PAL(x) is equal to 0 if otherwise. That is, PAL(x) = 1 if and only if x1x2...xn = xnxn-1...x1. Assuming that there is a TM M that can compute PAL within less than 3n steps, and this TM M uses 3 tapes (input, work and output) and the alphabet { Δ , □ , 0, 1}, with the following algorithm:
-Copy the input to the read-write work tape
-Move the input-tape head to the beginning of the input
-Move the input-tape head to the right while moving the work-tape head to the left. At any moment if the value from the input-tape is not the same as the value from the work-tape, the machine will halts and output 0 to the output-tape
-If the machine observes the end symbol from the input-tape or the start symbol from the work-tape, the machine will halts and output 1 to the output-tape
'''Originally Posted By: stang'''
Q2: <br>Give a TM algorithm for computing palindrome.<br><br>Answer: <br>Let PAL be a Boolean function which for every x ∈ {0, 1} ⋆, PAL(x) is equal to 1 if x is a palindrome and PAL(x) is equal to 0 if otherwise. That is, PAL(x) = 1 if and only if x1x2...xn = xnxn-1...x1. Assuming that there is a TM M that can compute PAL within less than 3n steps, and this TM M uses 3 tapes (input, work and output) and the alphabet { Δ , □ , 0, 1}, with the following algorithm:<br>-Copy the input to the read-write work tape<br>-Move the input-tape head to the beginning of the input<br>-Move the input-tape head to the right while moving the work-tape head to the left. At any moment if the value from the input-tape is not the same as the value from the work-tape, the machine will halts and output 0 to the output-tape<br>-If the machine observes the end symbol from the input-tape or the start symbol from the work-tape, the machine will halts and output 1 to the output-tape
Originally Posted By: miao
10. Prove that TAUTOLOGY is coNP complete.
Please read the attachment.
Please read the attachment.
'''Originally Posted By: miao'''
10. Prove that TAUTOLOGY is coNP complete.<br>Please read the attachment.
2011-10-02
Originally Posted By: snigdhamokkapati
Problem 8:
Verifier formulation of NP class:
A language L⊆{0,1}* is in NP if there exists a polynomial p:ℕ→ℕ and a polynomial time TM M (called the verifier for L) such that for every x∈{0,1}*,
x∈L⇔∃u∈{0,1}^p(|x|) s. t. M(x,u)=1
If x∈L we call a u∈{0,1}^p(|x|) such that M(x,u)=1 a certificate.
This certificate definition of NP was not the original definition of the class NP. Instead when NP was first defined, it was defined as a class of languages accepted by non-deterministic TMs.
Formulation of NP class using non-deterministic turing machines:
For every function T:ℕ→ℕ and L⊆{0,1}*, we say that L∈NTIME(T(n)) if there is a constant c>0 and a c⋅T(n)-time NDTM M such that for every x∈{0,1}*, x∈L⇔M(x)=1.
However, it can be proved that the two definitions coincide.
Theorem: NP=∪c∈ℕ NTIME(n^c).
Proof:
The main idea of the proof is that the sequence of non-deterministic choices made by a NDTM N on an accepting computation of an input x ( i.e N(x) = 1) can be viewed as a certificate that the input is in the language L (i.e x∈L ) and vice-versa.
Suppose p is polynomial p: ℕ→ℕ and N is a NDTM that decides L in time p(n). For every x∈L, N makes a series of non-deterministic choices and reaches qaccept state on input x. This sequence of non-deterministic choices made by N can be encoded as a string u in {0, 1}^p(|x|). Now a deterministic polynomial time TM M can take as input x and string u (which will act like a certificate) and it can simulate the NDTM N using string u and can verify if N entered qaccept. If it entered qaccept, M(x, u) = 1 which implies L ∈ NP.
Conversely, if L ∈ NP, we can come up with a NDTM N that decides L in the following manner. On input x, first N uses its ability to make non-deterministic choices to write down a string u of length p(|x|) on one of its work tapes. Then N runs the deterministic algorithm of verifier M (used in the verifier formulation of NP) to check if this string u is a valid certificate on input x. If it is N enters qaccept.
Verifier formulation of NP class:
A language L⊆{0,1}* is in NP if there exists a polynomial p:ℕ→ℕ and a polynomial time TM M (called the verifier for L) such that for every x∈{0,1}*,
x∈L⇔∃u∈{0,1}^p(|x|) s. t. M(x,u)=1
If x∈L we call a u∈{0,1}^p(|x|) such that M(x,u)=1 a certificate.
This certificate definition of NP was not the original definition of the class NP. Instead when NP was first defined, it was defined as a class of languages accepted by non-deterministic TMs.
Formulation of NP class using non-deterministic turing machines:
For every function T:ℕ→ℕ and L⊆{0,1}*, we say that L∈NTIME(T(n)) if there is a constant c>0 and a c⋅T(n)-time NDTM M such that for every x∈{0,1}*, x∈L⇔M(x)=1.
However, it can be proved that the two definitions coincide.
Theorem: NP=∪c∈ℕ NTIME(n^c).
Proof:
The main idea of the proof is that the sequence of non-deterministic choices made by a NDTM N on an accepting computation of an input x ( i.e N(x) = 1) can be viewed as a certificate that the input is in the language L (i.e x∈L ) and vice-versa.
Suppose p is polynomial p: ℕ→ℕ and N is a NDTM that decides L in time p(n). For every x∈L, N makes a series of non-deterministic choices and reaches qaccept state on input x. This sequence of non-deterministic choices made by N can be encoded as a string u in {0, 1}^p(|x|). Now a deterministic polynomial time TM M can take as input x and string u (which will act like a certificate) and it can simulate the NDTM N using string u and can verify if N entered qaccept. If it entered qaccept, M(x, u) = 1 which implies L ∈ NP.
Conversely, if L ∈ NP, we can come up with a NDTM N that decides L in the following manner. On input x, first N uses its ability to make non-deterministic choices to write down a string u of length p(|x|) on one of its work tapes. Then N runs the deterministic algorithm of verifier M (used in the verifier formulation of NP) to check if this string u is a valid certificate on input x. If it is N enters qaccept.
'''Originally Posted By: snigdhamokkapati'''
Problem 8:<br><br>Verifier formulation of NP class:<br>A language L⊆{0,1}* is in NP if there exists a polynomial p:ℕ→ℕ and a polynomial time TM M (called the verifier for L) such that for every x∈{0,1}*,<br>x∈L⇔∃u∈{0,1}^p(|x|) s. t. M(x,u)=1<br>If x∈L we call a u∈{0,1}^p(|x|) such that M(x,u)=1 a certificate. <br><br>This certificate definition of NP was not the original definition of the class NP. Instead when NP was first defined, it was defined as a class of languages accepted by non-deterministic TMs.<br><br>Formulation of NP class using non-deterministic turing machines:<br>For every function T:ℕ→ℕ and L⊆{0,1}*, we say that L∈NTIME(T(n)) if there is a constant c>0 and a c⋅T(n)-time NDTM M such that for every x∈{0,1}*, x∈L⇔M(x)=1.<br><br>However, it can be proved that the two definitions coincide.<br>Theorem: NP=∪c∈ℕ NTIME(n^c).<br>Proof:<br>The main idea of the proof is that the sequence of non-deterministic choices made by a NDTM N on an accepting computation of an input x ( i.e N(x) = 1) can be viewed as a certificate that the input is in the language L (i.e x∈L ) and vice-versa.<br><br>Suppose p is polynomial p: ℕ→ℕ and N is a NDTM that decides L in time p(n). For every x∈L, N makes a series of non-deterministic choices and reaches qaccept state on input x. This sequence of non-deterministic choices made by N can be encoded as a string u in {0, 1}^p(|x|). Now a deterministic polynomial time TM M can take as input x and string u (which will act like a certificate) and it can simulate the NDTM N using string u and can verify if N entered qaccept. If it entered qaccept, M(x, u) = 1 which implies L ∈ NP.<br><br>Conversely, if L ∈ NP, we can come up with a NDTM N that decides L in the following manner. On input x, first N uses its ability to make non-deterministic choices to write down a string u of length p(|x|) on one of its work tapes. Then N runs the deterministic algorithm of verifier M (used in the verifier formulation of NP) to check if this string u is a valid certificate on input x. If it is N enters qaccept.
Originally Posted By: nkeerthy
Problem 9 Give a p-time reduction from 3SAT to INDEPENDENT SET.
Solution
INDSET is in NP since if we guess a subset of k nodes of G we can in p-time verify whether they form an independent set. To show INDSET is NP-complete we reduce 3SAT to it. Let ∧Ci be an instance of 3SAT where each Ci is a clause. There is exactly one assignment of the variables in a given Ci which will make it false. For each clause, we make a clique out of seven vertices each vertex labelled with the name of the clause and a satisfying true assignment for that clause. For any given clause at most one of these vertices can be in an independent set. To this initial graph we then add edges between vertices in cliques corresponding to different clauses if the assignments on the vertices labels conflict. Finally, if our input 3SAT instance has m clauses, we ask if the resulting graph has an independent set of size m. This reduction is at most quadratically larger than the input instance and computationally easy to compute (so p-time). Notice each vertex in such an independent set must belong to a distinct clause-clique of which there are m. Further if there is a satisfying for the 3SAT instance, there the values of that assignment in each clause will correspond to a clause-clique vertices that don't share any edges. So in this case, there will be an independent set of size m. Similarly, if there is an independent set of size m all of its members must belong to different clause-cliques and there vertex labels must no correspond to conflicting assignments. So from these labels we could read off a truth assignment for the 3SAT instance.
Solution
INDSET is in NP since if we guess a subset of k nodes of G we can in p-time verify whether they form an independent set. To show INDSET is NP-complete we reduce 3SAT to it. Let ∧Ci be an instance of 3SAT where each Ci is a clause. There is exactly one assignment of the variables in a given Ci which will make it false. For each clause, we make a clique out of seven vertices each vertex labelled with the name of the clause and a satisfying true assignment for that clause. For any given clause at most one of these vertices can be in an independent set. To this initial graph we then add edges between vertices in cliques corresponding to different clauses if the assignments on the vertices labels conflict. Finally, if our input 3SAT instance has m clauses, we ask if the resulting graph has an independent set of size m. This reduction is at most quadratically larger than the input instance and computationally easy to compute (so p-time). Notice each vertex in such an independent set must belong to a distinct clause-clique of which there are m. Further if there is a satisfying for the 3SAT instance, there the values of that assignment in each clause will correspond to a clause-clique vertices that don't share any edges. So in this case, there will be an independent set of size m. Similarly, if there is an independent set of size m all of its members must belong to different clause-cliques and there vertex labels must no correspond to conflicting assignments. So from these labels we could read off a truth assignment for the 3SAT instance.
'''Originally Posted By: nkeerthy'''
Problem 9 Give a p-time reduction from 3SAT to INDEPENDENT SET. <br>Solution<br>INDSET is in NP since if we guess a subset of k nodes of G we can in p-time verify whether they form an independent set. To show INDSET is NP-complete we reduce 3SAT to it. Let ∧Ci be an instance of 3SAT where each Ci is a clause. There is exactly one assignment of the variables in a given Ci which will make it false. For each clause, we make a clique out of seven vertices each vertex labelled with the name of the clause and a satisfying true assignment for that clause. For any given clause at most one of these vertices can be in an independent set. To this initial graph we then add edges between vertices in cliques corresponding to different clauses if the assignments on the vertices labels conflict. Finally, if our input 3SAT instance has m clauses, we ask if the resulting graph has an independent set of size m. This reduction is at most quadratically larger than the input instance and computationally easy to compute (so p-time). Notice each vertex in such an independent set must belong to a distinct clause-clique of which there are m. Further if there is a satisfying for the 3SAT instance, there the values of that assignment in each clause will correspond to a clause-clique vertices that don't share any edges. So in this case, there will be an independent set of size m. Similarly, if there is an independent set of size m all of its members must belong to different clause-cliques and there vertex labels must no correspond to conflicting assignments. So from these labels we could read off a truth assignment for the 3SAT instance.
Originally Posted By: Nishant
Ans-6
Let
F= (~(a v b)) ^(c v d) where ^->AND , ~ -> Negation, v -> OR
For truth assignment of a, b, c and d as follows a=b=0; c=d=1
F outputs 1.
The idea is to prove that this verification can be done in polynomial time. We can prove this by drawing the tree of the expression and use the truth assignments of the variables and check the value at each gate. This can be done in polynomial time hence it is in P.
Let
F= (~(a v b)) ^(c v d) where ^->AND , ~ -> Negation, v -> OR
For truth assignment of a, b, c and d as follows a=b=0; c=d=1
F outputs 1.
The idea is to prove that this verification can be done in polynomial time. We can prove this by drawing the tree of the expression and use the truth assignments of the variables and check the value at each gate. This can be done in polynomial time hence it is in P.
'''Originally Posted By: Nishant'''
Ans-6<br>Let<br>F= (~(a v b)) ^(c v d) where ^->AND , ~ -> Negation, v -> OR<br><br>For truth assignment of a, b, c and d as follows a=b=0; c=d=1 <br>F outputs 1.<br><br>The idea is to prove that this verification can be done in polynomial time. We can prove this by drawing the tree of the expression and use the truth assignments of the variables and check the value at each gate. This can be done in polynomial time hence it is in P.
(c) 2024 Yioop - PHP Search Engine