2011-11-06
Midterm 2 questions 7 and 8.
Originally Posted By: Jay_Reynolds_Freeman
Submitted by Jay Freeman, who worked on these problems with Nishant Patel:
Problem 7:
To show NL contained in CoNL, let L be a language in NL, and x be a string in L. Then since PATH is known to be NL-complete, there is a log-space reduction of x to some f(x) which is in PATH. And since PATH is by hypothesis in CoNL, it follows that a TM which first runs the reduction and then the CoNL decision TM for PATH will run in logspace, and the existence of that TM shows that L is in CoNL.
To show that CoNL is contained in L, let L be in CoNL. It follows that L-bar is in NL, but since we have just shown that NL is contained in CoNL, L-bar is in CoNL, which means in turn that (L-bar)-bar is in NL, but (L-bar)-bar is just L, which completes the proof.
Problem 8:
To show that Sigma-p-i is in U-c-... : Let L be a language in Sigma-p-i, which involves a Turing machine M. We set up a scratch tape with space enough on it for all of the quantified variables, and take whatever time we need to write out and try all of the combinations of those variables, to see whether some combination satisfies all the quantifications. We arrange that our TM to try the variables tries the elements of the first "exists" quantifier in order, then the first "forall" quantifier, then the second "exists", and so on; that is, a path through its configuration graph so to speak gathers up a particular set of variables and then runs the original TM for L on them. The configuration graph for this TM thus alternates i-1 times. The time to run any one path of this new TM is the total number of quantified variables plus the time to run the original TM for L -- that was "M", hence the time to run it it is in n**c where c is the degree of the polynomial time for M.
In the other direction, let L be a language in Sigma-i( n**c ) for some i and c. We imagine each path through its configuation graph divided into stages corresponding to the successive runs of similarly quantified variables. We construct a new configuration graph in which each stage of each path is padded to include the union of all variables encountered in that stage of any path (some of which may not matter in any particular path). The TM represented by this latter graph is in the form required for the definition of Sigma-p-i -- each stage of each path contains the same quantified set of variables. The additional time required to traverse the extra variables on any given path cannot exceed i * n (since we cannot get more than n variables when we take the union), so the time required to run the new TM is either still n**c if c was originally greater than or equal to one, or is n**1 if the original c was zero, and we are done.
Problem 7:
To show NL contained in CoNL, let L be a language in NL, and x be a string in L. Then since PATH is known to be NL-complete, there is a log-space reduction of x to some f(x) which is in PATH. And since PATH is by hypothesis in CoNL, it follows that a TM which first runs the reduction and then the CoNL decision TM for PATH will run in logspace, and the existence of that TM shows that L is in CoNL.
To show that CoNL is contained in L, let L be in CoNL. It follows that L-bar is in NL, but since we have just shown that NL is contained in CoNL, L-bar is in CoNL, which means in turn that (L-bar)-bar is in NL, but (L-bar)-bar is just L, which completes the proof.
Problem 8:
To show that Sigma-p-i is in U-c-... : Let L be a language in Sigma-p-i, which involves a Turing machine M. We set up a scratch tape with space enough on it for all of the quantified variables, and take whatever time we need to write out and try all of the combinations of those variables, to see whether some combination satisfies all the quantifications. We arrange that our TM to try the variables tries the elements of the first "exists" quantifier in order, then the first "forall" quantifier, then the second "exists", and so on; that is, a path through its configuration graph so to speak gathers up a particular set of variables and then runs the original TM for L on them. The configuration graph for this TM thus alternates i-1 times. The time to run any one path of this new TM is the total number of quantified variables plus the time to run the original TM for L -- that was "M", hence the time to run it it is in n**c where c is the degree of the polynomial time for M.
In the other direction, let L be a language in Sigma-i( n**c ) for some i and c. We imagine each path through its configuation graph divided into stages corresponding to the successive runs of similarly quantified variables. We construct a new configuration graph in which each stage of each path is padded to include the union of all variables encountered in that stage of any path (some of which may not matter in any particular path). The TM represented by this latter graph is in the form required for the definition of Sigma-p-i -- each stage of each path contains the same quantified set of variables. The additional time required to traverse the extra variables on any given path cannot exceed i * n (since we cannot get more than n variables when we take the union), so the time required to run the new TM is either still n**c if c was originally greater than or equal to one, or is n**1 if the original c was zero, and we are done.
'''Originally Posted By: Jay_Reynolds_Freeman'''
Submitted by Jay Freeman, who worked on these problems with Nishant Patel:<br><br>Problem 7:<br><br>To show NL contained in CoNL, let L be a language in NL, and x be a string in L. Then since PATH is known to be NL-complete, there is a log-space reduction of x to some f(x) which is in PATH. And since PATH is by hypothesis in CoNL, it follows that a TM which first runs the reduction and then the CoNL decision TM for PATH will run in logspace, and the existence of that TM shows that L is in CoNL.<br><br>To show that CoNL is contained in L, let L be in CoNL. It follows that L-bar is in NL, but since we have just shown that NL is contained in CoNL, L-bar is in CoNL, which means in turn that (L-bar)-bar is in NL, but (L-bar)-bar is just L, which completes the proof.<br><br>Problem 8:<br><br>To show that Sigma-p-i is in U-c-... : Let L be a language in Sigma-p-i, which involves a Turing machine M. We set up a scratch tape with space enough on it for all of the quantified variables, and take whatever time we need to write out and try all of the combinations of those variables, to see whether some combination satisfies all the quantifications. We arrange that our TM to try the variables tries the elements of the first "exists" quantifier in order, then the first "forall" quantifier, then the second "exists", and so on; that is, a path through its configuration graph so to speak gathers up a particular set of variables and then runs the original TM for L on them. The configuration graph for this TM thus alternates i-1 times. The time to run any one path of this new TM is the total number of quantified variables plus the time to run the original TM for L -- that was "M", hence the time to run it it is in n**c where c is the degree of the polynomial time for M.<br><br>In the other direction, let L be a language in Sigma-i( n**c ) for some i and c. We imagine each path through its configuation graph divided into stages corresponding to the successive runs of similarly quantified variables. We construct a new configuration graph in which each stage of each path is padded to include the union of all variables encountered in that stage of any path (some of which may not matter in any particular path). The TM represented by this latter graph is in the form required for the definition of Sigma-p-i -- each stage of each path contains the same quantified set of variables. The additional time required to traverse the extra variables on any given path cannot exceed i * n (since we cannot get more than n variables when we take the union), so the time required to run the new TM is either still n**c if c was originally greater than or equal to one, or is n**1 if the original c was zero, and we are done.
(c) 2024 Yioop - PHP Search Engine