Computational tameness of classical non-causal models

Area of Science:

• Theoretical computer science
• Quantum computing
• Cosmology

Background:

• The computational power of non-causal systems, particularly closed timelike curves (CTCs), is a subject of theoretical interest.
• Previous models suggested CTCs could efficiently solve NP-complete problems, raising questions about their physical plausibility.

Purpose of the Study:

• To precisely characterize the computational power of classical deterministic CTCs.
• To determine if these CTCs can efficiently solve problems outside the UP∩coUP complexity class.

Main Methods:

• Analysis of the non-causal circuit model, replacing global causality with logical consistency.
• Characterization of computational power using complexity classes, specifically UP∩coUP.
• Investigation of the implications for solving NP-complete problems.

Main Results:

• The computational power of the non-causal circuit model is fully characterized by the complexity class UP∩coUP.
• Factorization is an example of a problem solvable within this class.
• Classical deterministic CTCs cannot efficiently solve problems outside UP∩coUP.

Conclusions:

• Classical deterministic CTCs are restricted to solving problems within UP∩coUP, unlike some other CTC models.
• These CTCs cannot efficiently solve NP-complete problems unless NP=UP∩coUP=coNP.
• The limited computational power makes the existence of these specific CTCs in nature appear less implausible.