Prove the following: A language X is the language of an alternating TM with O(logn) space...

 

Transcribed Image Text:

Prove the following: A language X is the language of an alternating TM with O(logn) space and O(1) alternations if and only if X is in NL. Easy Warm-up #2: A boolean circuit is called a formula if its directed graph is a tree. In Lecture 13.4 we proved that any polynomial-size formula is equivalent to some NC circuit. Here we ask you to prove that any NC circuit is equivalent to a polynomial-size formula, which also has O(log n) depth. Prove the following: A language X is the language of an alternating TM with O(logn) space and O(1) alternations if and only if X is in NL. Easy Warm-up #2: A boolean circuit is called a formula if its directed graph is a tree. In Lecture 13.4 we proved that any polynomial-size formula is equivalent to some NC circuit. Here we ask you to prove that any NC circuit is equivalent to a polynomial-size formula, which also has O(log n) depth.

Answer rating: 100% (QA)

Forward direction X is in NL implies Xis the language of an alternati... View the full answer