University of Cambridge > > Churchill CompSci Talks > Closed Timelike Curves and Complexity Theory

Closed Timelike Curves and Complexity Theory

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Matthew Ireland.

From DeLoreans to police boxes and hot tubs, Science Fiction has provided many machines capable of time-travel. Whilst a powerful tool for learning from observation of other times, the causal flow of information can become somewhat distorted by the ability to send it back to before its generation. One question of time-travel that Science Fiction has not answered for us is whether or not there are any gains in computational power to be had by embedding a flux capacitor into the humble Turing machine.

Closed Timelike Curves describe a theoretical model of consistency for regions of space-time in the presence of time-travel. We shall discuss the uses of Deutschian CTCs in finding a solution to the Grandfather paradox and how to exploit the consistency requirements in circuit design allowing time-travel. In doing this, we shall cover some basic techniques used in complexity-theoretic analysis, define the complexity class P_CTC (problems that can be solved in polynomial time using circuits with CTCs) and prove that, rather surprisingly, this is equivalent to PSPACE .

This talk is part of the Churchill CompSci Talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity