tag:blogger.com,1999:blog-3722233.post112294647498287275..comments2024-03-29T08:55:55.727-05:00Comments on Computational Complexity: Relativizing SpaceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-87695637984817822362021-07-08T14:59:40.563-05:002021-07-08T14:59:40.563-05:00"2. a nondeterministic (or probabilistic or q..."2. a nondeterministic (or probabilistic or quantum) machine must act deterministically while writing on the oracle tape."<br /><br />So copying from certificate tape is forbidden?<br /><br />Only copying from input tape is allowed?Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32219798673470760042021-07-08T14:46:47.249-05:002021-07-08T14:46:47.249-05:00So modular exponentiation in nc implies discrete l...So modular exponentiation in nc implies discrete logarithm in quasiP? Does modular exponentiation in any o(n) space polytime algorithm have relation to natural proofs barrier?Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41321957604313497652021-07-08T14:40:31.573-05:002021-07-08T14:40:31.573-05:00"You want a log-space bounded machine to at l..."You want a log-space bounded machine to at least write its own input on the oracle tape but you don't want the tape to be used as auxiliary storage." <br /><br />Given a witness on a read once certificate tape am I allowed to copy contents certificate to query?<br /><br />---------<br /><br />Problem find x in g^x=h mod p.<br /><br />Read once certificate tape has witness x in binary.<br /><br />Assumption: g^{2^i x_i} mod p is in NC1 where x_i is ith bit.<br /><br />Cannot I scan the certificate tape from left to right and compute g^{2^i x_i} mod p accordingly and write to query tape and call a Logspace machine which does iterated multiplication which is in TC0 and calls another logspace machine to compute mod p?<br /><br />Similar strategy can place discrete logarithm in NL^i if modular exponentiation is in NC^i. Correct?<br />Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.com