Closed Timelike Curves and Complexity Theory

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

• William Simmons, St Catharine's College
• Wednesday 30 November 2016, 19:30-20:00
• Wolfson Hall, Churchill College.

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.

This talk is included in these lists:

• Churchill CompSci Talks
• Wolfson Hall, Churchill College
• computer science
• se393's list

Note that ex-directory lists are not shown.