Abstract:
Discussions of Closed Timelike Curves (CTC) led to a few computation models that when used in conjunction with a Turing Machine, yield much more efficient com putations. CTC assisted computation has the ability to send a piece of information back in time which breaks the time causality and has various paradoxes associated with it. Computation models deal with these paradoxes differently by making different assumptions. Regardless of the practicality of CTCs, studying different computation models has the possibility to grant valuable insight into complexity classes and their relationships among each other. The first of these models is proposed by Deutsch. The model avoids paradoxes by assuming that the states that enter and exit the machine constitute a probabil ity distribution and that the machine outputs a stationary distribution. The second model, proposed by Lloyd et al. has the ability to discard unwanted outcomes, via the assumption of time-related paradoxes that can be caused by CTC interaction to be impossible. The third model, proposed by Say and Yakaryılmaz improves upon Deutsch’s model and deals with some of its shortcomings. In this thesis, we demonstrate and analyze how these CTC based computation models help solve NP-complete, and some other problems efficiently and propose a more cost-efficient version of one such algorithm from the literature. Lastly, we explore and discuss some odd and interesting properties of calculations in DCTCs.
