Computation with narrow CTCs

Details Computation with narrow CTCs Computation with narrow CTCs

2011-02-06

arxiv.org/abs/1102.1199v2

Computer Science

Computational Complexity

16 pages. A few typo was corrected

Scientific paper

We examine some variants of computation with closed timelike curves (CTCs), where various restrictions are imposed on the memory of the computer, and the information carrying capacity and range of the CTC. We give full characterizations of the classes of languages recognized by polynomial time probabilistic and quantum computers that can send a single classical bit to their own past. Such narrow CTCs are demonstrated to add the power of limited nondeterminism to deterministic computers, and lead to exponential speedup in constant-space probabilistic and quantum computation. We show that, given a time machine with constant negative delay, one can implement CTC-based computations without the need to know about the runtime beforehand.

Affiliated with

Also associated with

No associations

Rating

Computation with narrow CTCs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computation with narrow CTCs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computation with narrow CTCs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-680364