## Abstract

We show that the computational power of the non-causal circuit model, i.e. the circuit model where the assumption of a *global causal order* is replaced by the assumption of *logical consistency*, is completely characterized by the complexity class UP∩coUP. An example of a problem in that class is factorization. Our result implies that classical deterministic closed timelike curves (CTCs) cannot efficiently solve problems that lie *outside* of that class. Thus, in stark contrast to other CTC models, these CTCs *cannot* efficiently solve NP-complete problems, unless NP=UP∩coUP=coNP, which lets their existence in nature appear *less implausible*. This result gives a new characterization of UP∩coUP in terms of fixed points.

## 1. Motivation and results

The *acyclic* feature of ‘causality’ [1], that an effect cannot be the cause of its cause, plays a central role in everyday live, physical theories and models of computation. A *cyclic* causal structure is—in the classical meaning^{1} of the following adjective—paradoxical. That may be a reason for why an *acyclic* notion is not only preferred but also a hidden assumption for many theories. Objections against *cyclic* causal structures are the *grandfather antinomy* and the *uniqueness ambiguity*^{2} (e.g. [2–4]). The former reads: by travelling to the past and killing his or her own grandfather, one could never have been born to travel to the past to kill his or her own grandfather—an *inconsistency*. The latter is *ex nihilo* appearance of information, as illustrated in the following example. Assume one morning you wake up to find a proof of P=NP on your desk. You decide to publish it and, after publication, you travel back in time to the night before you found the proof to place the original copy on your desk, while your younger self is asleep. Who wrote the proof? More precisely, the uniqueness ambiguity arises when ‘an uncomputed output is produced’, in the sense that some ‘theory specifies more the one final state given some initial state and evolution, but fails to give probabilities for each possibility’ [4]. However, if the proof you find on your desk is *uniquely* determined by a process, then the proof does not appear *ex nihilo*, but is the *result* of that process. The uniqueness ambiguity is often considered *less severe* than the grandfather antinomy. But note that, according to Deutsch [5], solutions to problems need to emerge through evolutionary or rational processes; otherwise, the underlying theory would follow the *doctrine of creationism*. By this, uniqueness ambiguities ‘contradict the philosophy of science’. Note that both problems are similar in their spirit; the grandfather antinomy, in accordance to Allen’s [4] formulation of the uniqueness ambiguity, reads: the grandfather antinomy arises whenever a theory fails to specify *any consistent* final state given some initial state and evolution. In the following, we will refer to a model as being *logically consistent* whenever both problems do not arise.

Closed timelike curves (CTCs) are loops in space–time (figure 1*a*). That is, by travelling on such a curve, one would bump into oneself on the same position in space *and* time. Interestingly, CTCs appear as solutions to Einstein’s equations of general relativity (e.g. [8–14]), yet they have been or still are believed to be unphysical; their underlying structure is *cyclic*. For over 20 years, people have studied different models of CTCs and their implications. Scientists around Novikov and Thorne [15–19] analysed CTCs in the gravitational setting and found self-consistent dynamics for all initial conditions considered. In more detail, they studied the trajectories of objects like billiard balls that, once the initial conditions of the objects have been specified (that is, on the surface *a*), travel trough CTCs and bounce off themselves. Their result is surprising: *multiple*, as opposed to *zero* (‘to one’s naive expectation’ [16]), self-consistent trajectories to initial conditions that lead to self-collisions were found. Self-*in*consistent trajectories are simply neglected by the means of Novikov’s principle of self-consistency [15]. While the grandfather antinomy is avoided, the uniqueness ambiguity persists. Deutsch [5] analysed CTCs in the quantum information realm and showed that there, the grandfather antinomy never occurs. Because *multiple* consistent states to some initial conditions exist, Deutsch singles out the mixture of all consistent states that maximizes the entropy as the solution; by this he mitigates the uniqueness ambiguity. This maximum-entropy strategy, however, has a price: the evolution becomes nonlinear. So, the self-consistent state might be a mixed state, by which one is forced to consider mixed states as *ontic*. This means that the states of the systems travelling on Deutsch CTCs describe ‘reality’ as opposed to the *knowledge of an observer about a system* [20]. Bennett *et al.* [21] criticized the results on the computational power of Deutsch CTCs by pointing at a ‘linearity trap’: if one uses a mixture of problems as input to some CTC, one is not given the mixture of the solutions. By this, in similar spirit to our work and to Baumeler *et al.* [7], they define a (possibly weaker) CTC model where input–output pairs are correlated correctly. Note that the present result is not akin to the ‘linearity trap’, as our underlying models are linear. Pegg [22] and other researchers [23–27] designed a different model of CTCs, in which states are sent with the help of quantum teleportation to the past (via postselection). That model, however, also leads to a nonlinear evolution. Recently, Oreshkov *et al.* [28] came up with a framework for quantum correlations without global causal order. There, the main assumptions are *linearity* and *local validity* of quantum theory. Interestingly, the framework describes correlations that cannot be simulated with a *global* causal order [7,28–30], and allows for advantages in query [31–35], as well as communication complexity [36,37]. The classical special case [38] of that framework was shown to allow for *classical deterministic CTCs* [7] where both problems (grandfather antinomy and uniqueness ambiguity) *never* arise;^{3} therefore, we refer to these CTCs as *logically consistent CTCs*. The main conceptual difference to the works by Novikov and Thorne are that in set-ups with logically consistent CTCs, experimenters are *free* to manipulate the classical systems that travel on CTCs, as opposed to be restricted in only choosing the *initial conditions* (figure 1*b*). One can also define a *non-causal circuit model* of computation [40] based on the assumption that both problems are avoided. Here, we characterize the computational power of that circuit model which yields, as we are going to show, an upper bound on the computational power of *classical deterministic CTCs*.

Even though we do not know whether CTCs exist in nature or not, we can study their consequences. As Aaronson [41] put it, one could assume that nature *cannot* efficiently solve certain tasks (e.g. NP-hard problems), in the same spirit as nature cannot signal faster than at the speed of light, and conclude that certain theories are *un*physical. The same idea is used in reconstructions of quantum theory where the standard, unintuitive axioms are replaced by ‘more natural’ ones (see [42] for a collection of such reconstructions). As it turns out [43], the class P_{CTC} of all problems solvable in polynomial time by classical Deutsch CTCs is equal to its quantum analogue BQP_{CTC}, and furthermore, equal to PSPACE.^{4} Most recently, Aaronson *et al.* [47] showed that the Deutsch model can even solve the halting problem. The model of CTCs where the loops are generated through quantum teleportation to the past can efficiently solve all problems in the class PostBQP=PP [25,48,49]. The classical analogue thereof can efficiently solve problems in PostBPP=BPP_{path} [25,50]. The inclusion relations between these classes are NP⊆PostBPP⊆PostBQP⊆P_{CTC}⊆EXP, where *strict* inclusions are conjectured. Our contribution is to show
_{NCCirc} (NCCirc standing for ‘non-causal circuit’) of decision problems solvable in polynomial time with the *non-causal circuit model* is equal to UP∩coUP, and furthermore that P_{LCCTC}, which represents the power of classical computation equipped with logically consistent CTCs [7], is upper bounded by this class. The class UP∩coUP contains all decision problems where for each possible answer (‘yes’ or ‘no’) a *unique* witness exists. Examples of such problems are integer factorization [51] and parity games [52], casted as decision problems. Thus, this class is of great importance to the field of cryptography. Moreover, it was shown [53] that worst-case one-way permutation exist if and only if P≠UP∩coUP. Figure 2 depicts the inclusion relations among the mentioned complexity classes: P⊆P_{LCCTC}⊆P_{NCCirc}⊆NP⊆PostBPP⊆PostBQP⊆P_{CTC}. The logically consistent CTCs [7] are the weakest of all known CTCs in terms of computation, and are *unable* to efficiently solve NP-complete problems (unless NP=UP∩coUP, which implies NP=coNP, by which the polynomial hierarchy would collapse to the first level [54], which is highly doubted). We also show the analogue statement for *search* problems:
*unique* solutions. Furthermore, these results give an interpretation of the classes UP∩coUP and TFUP in terms of *fixed points*: every instance of such a problem can be solved by finding the *unique* deterministic fixed point of a transformation computable in polynomial time.

This work is organized as follows. First, we describe the computational model, and, after that, we define some complexity classes and present our results. Then, we present an example on how to factorize integers by using that model, give conclusions and state some open problems.

## 2. Model of computation

Classical deterministic CTCs that are free of the grandfather antinomy and the uniqueness ambiguity were studied in [7]. There it was shown that such CTCs are logically possible even in the case where *N* parties sitting in localized regions can *freely* interact with the systems travelling on the CTCs. We ask the reader to consult figure 3 with the following description of the CTC model. Let *j*≤*N*. Party *j* implements some function *f*_{j} of her *choice* from the set *N* parties implement some function *collection* of objects in all *N* regions, e.g. ^{5}
*any choice* of the local operations results in a function that has a *unique* deterministic fixed point. This is easily interpreted: if for some choice of local operations there would be *no* fixed point, then the grandfather antinomy is reproduced, if there are *more than one* fixed points, then the uniqueness ambiguity is reproduced. For three or more local regions, such antinomy-free CTCs become possible [7] (in the sense that there exist local operations and ‘process functions’ where a region necessarily is *in the past and in the future* of every other region.

The non-causal circuit model [40], then again, is formulated in terms of *gates* as opposed to *parties* and ‘process functions’. A *circuit* is a collection of gates that are connected in an acyclic fashion, and where the input and output wires are numbered from 1 on upwards in integer steps (figure 4*a*). Without loss of generality, and if not otherwise stated, we assume that every wire carries a bit. A *closed circuit* is a circuit without input and without output wires. A circuit *b*). The introduced connections can be thought as ‘back in time’—in the same spirit as the ‘back in time’ connections in CTC models. Let ^{n}, where *n* is the number of input bits to *C*). We call a closed circuit *logically consistent* if and only if *fixed* whereas for the CTCs, every party can *arbitrarily* choose her local operation. Thus, we omit the all quantifier in the logical-consistency condition for circuits (compare the above equation with equation (2.1)). Logically consistent closed circuits can be used to find unique fixed points, which is exploited in what follows.

## 3. Complexity classes

A *decision problem* *Π* is often casted as the membership problem of a language *L*⊆*Σ** with alphabet *Σ*. For simplicity, and without loss of generality, we choose *Σ*={0,1}. An instance of *Π* is a string *x*∈*Σ**, and the question is: is *x* a word of *L*, i.e. does *x*∈*L* hold? An algorithm that solves a decision problem outputs either ‘yes’ or ‘no’.

*Search problems*, then again, are mostly defined via binary relations. A problem *Π* is associated with a binary relation *R*⊆*Σ**×*Σ**. An instance of *Π* is some *x*∈*Σ**, and the question is: *What* (if there exists one) is *y*∈*Σ** such that (*x*,*y*)∈*R*? An algorithm that solves a search problem outputs *y* if there exists a *y* satisfying (*x*,*y*)∈*R* and returns ‘no’ otherwise.

We use |*x*| to denote the length of some string *x*∈*Σ**. A binary relation *R* is called *polynomially decidable* if there exists a deterministic Turing machine deciding the language {(*x*,*y*)∈*R*} in polynomial time, and *R* is called *polynomially balanced* if there exists some polynomial *q* such that (*x*,*y*)∈*R* implies |*y*|≤*q*(|*x*|).

In the following definitions of complexity classes, we require that for every problem *Π* and given a string *x*∈*Σ**, we can check in polynomial time whether *x* is an instance of *Π* or not. If *x* is *not* an instance of *Π*, then we abort. We refer the reader to Papadimitriou [55] and Arora & Barak [56] for common concepts in complexity theory.

### Definition 3.1 (Deterministic NCCirc algorithm).

A *deterministic NCCirc algorithm* *x*∈{0,1}* and outputs a Boolean circuit *x* the closed circuit *y* has the form *y*=1*z* for some *z*, then we say *accepts* *x*, otherwise, *rejects* *x*. The algorithm *decides a language* *L*⊆{0,1}* if *x*∈*L* and rejects every *x*∉*L*. Furthermore, the algorithm *decides a binary relation* *R*⊆{0,1}*×{0,1}* if for every *x*∈{0,1}* the pair (*x*,*y*), with *c*_{x}(*y*)=*y*, is in *R*.

Based on the above definition, we define the complexity classes P_{NCCirc} and FP_{NCCirc}.

### Definition 3.2 (P_{NCCirc} and FP_{NCCirc}).

The class P_{NCCirc} contains all languages decidable by some deterministic NCCirc algorithm. The class FP_{NCCirc} contains all binary relations decidable by some deterministic NCCirc algorithm.

We will relate P_{NCCirc} to the following complexity class.

### Definition 3.3 (UP).

The class UP (Unambiguous Polynomial time) contains all languages *L* for which a polynomial-time verifier *x*, if *x*∈*L* then ∃!*y*:*V* (*x*,*y*)=1, and if *x*∉*L* then ∀*y*:*V* (*x*,*y*)=0.

The complexity class UP was first defined by Valiant [57]. The only difference between the classes NP and UP is that in the former, *multiple* witnesses are allowed. The class coUP contains all languages *L* where the complement of *L* is in UP.

We are now ready to state our first theorem.

### Theorem 3.4

P_{NCCirc}*=*UP*∩*coUP.

### Proof.

We start by showing UP∩coUP⊆P_{NCCirc}. Assume a language *L* is in UP∩ coUP. Thus, there exist two polynomial time verifiers *V* _{yes} and *V* _{no} such that for every *x*, if *x*∈*L*, then
*L*. Upon receiving *x*∈{0,1}*, *V* _{yes},*V* _{no} and can be constructed in polynomial time, because *L* is assumed to be in UP∩coUP. The circuit acts in the following way:
*q* is a polynomial. The function *c*_{x} has a *unique* fixed point. If *x*∈*L*, then there exists a unique *w* with *V* _{yes}(*x*,*w*)=1, and *c*_{x}(1*w*)=1*w*. Otherwise, there exists a unique *w* with *V* _{no}(*x*,*w*)=1, and *c*_{x}(0*w*)=0*w*.

The converse (P_{NCCirc}⊆UP∩coUP) holds for the following reason. First, assume *L* is in P_{NCCirc}. This means that for every *x* we have some logically consistent circuit *V* _{yes} and *V* _{no} to act as
*z* is a fixed point of

A corollary of this theorem is that logically consistent CTCs cannot efficiently solve problems *outside* of the class UP∩coUP. To state this corollary, we first define the complexity class P_{LCCTC} of problems efficiently solvable by such CTCs.

### Definition 3.5 (Classical deterministic CTC algorithm and P_{LCCTC}).

A *classical deterministic CTC algorithm* *x*∈{0,1}* and outputs *N* (the number of parties in the CTC set-up), a list of non-negative integers (*m*_{1},*n*_{1},*m*_{2},*n*_{2},…,*m*_{N},*n*_{N}), where *f*_{1},*f*_{2},…,*f*_{N}) where *z*, then we say *accepts* *x*, otherwise, *rejects* *x*. The algorithm *decides a language* *L*⊆{0,1}* if *x*∈*L* and rejects every *x*∉*L*. The class P_{LCCTC} contains all languages decidable by some classical deterministic CTC algorithm.

The following inclusion relation follows immediately from the definitions and the theorem above.

### Corollary 3.6

P_{LCCTC}⊆UP∩coUP.

### Proof.

Assume a language *L* is in P_{LCCTC}. Then *L* is also in P_{NCCirc} as we can construct a logically consistent circuit *C* which has the induced function *c*= *w*°*f*. ▪

Finally, we discuss the respective search problems.

### Definition 3.7 (FUP).

A binary relation *R* is in FUP (Function UP) if and only if *R* is polynomially decidable, polynomially balanced and ∀*x*: |{*y* | (*x*,*y*)∈*R*}|≤1.

Informally, a problem is in FUP if for every instance there exists *at most* one solution.

### Definition 3.8 (F(UP∩coUP)).

A pair (*R*_{1},*R*_{2}) of relations is in F(UP∩coUP) if and only if both relations are polynomially decidable, polynomially balanced and for every instance *x*
*either* yet *not both* expressions to be true.

Note that the output of a search problem in F(UP∩coUP) is some string *w* that satisfies either (*x*,*w*)∈*R*_{1} or (exclusively) (*x*,*w*)∈*R*_{2} but, as we formulated it, does not tell us in *which* relation the pair (*x*,*y*) appears. However, since both relations are polynomially decidable, we can check in polynomial time whether *y* is a solution of *R*_{1} or *R*_{2}. This brings us to the following class, which is equal.

### Definition 3.9 (TFUP).

A binary relation *R* is in TFUP (totally FUP) if and only if *R* is polynomially decidable, polynomially balanced and ∀*x*,∃!*y*:(*x*,*y*)∈*R*.

### Theorem 3.10

TFUP*=*F(UP*∩*coUP).

### Proof.

Let *R* be a relation in TFUP and *R*_{1},*R*_{2} two relations such that for every *x*:
*R*_{1}=*R* and *R*_{2}=∅, and to show F(UP∩coUP)⊆TFUP, set *R*=*R*_{1}∪*R*_{2}. ▪

A similar statement TFNP=F(NP∩coNP) can also be made [58]. The complexity class TFNP is the class of all *total* relations that are polynomially decidable and polynomially balanced.

We now state and prove our last theorem.

### Theorem 3.11

FP_{NCCirc}*=*TFUP.

### Proof.

We start with TFUP⊆FP_{NCCirc}. A binary relation *R* in TFUP is polynomially decidable and polynomially balanced. Therefore, there exists an algorithm *x*,*y*, runs in polynomial time in |*x*|, and if (*x*,*y*)∈ *R* then *x* there exists a *unique* *y* with (*x*,*y*)∈*R*. The deterministic NCCirc algorithm *x*, generates the circuit *y*=*bz* with *b*∈{0,1}, then *y*′=(*b*⊕1)*z*. Thus, for every *x* we have a circuit *c*_{x}(*y*)=*y*⇒(*x*,*y*)∈*R*. The converse inclusion relation FP_{NCCirc}⊆TFUP is shown as follows. Suppose we are given a relation *R* that is decidable by a deterministic NCCirc algorithm *R* is polynomially decidable, polynomially balanced, and that every *x* has a *unique* solution. Indeed, *R* is polynomially decidable and polynomially balanced because *y* is computed in polynomial time in |*x*|. Furthermore, *unique* fixed point. The algorithm *R* on input *x* returns the truth value of *c*_{x}(*y*)=*y*. ▪

## 4. Example: integer factorization

We give an example of an algorithm to factorize integers. The NCCirc algorithm *p*_{1},*p*_{2},… along with its exponents *e*_{1},*e*_{2},…. We give a description of

Algorithm 1 takes as input 1 bit and 2*n* numbers in *K*={1,2,…,*N*−1}, where every number is represented as an *n*-bit string. On line 3, we check whether the first *n* numbers are ordered. On line 8, we check whether *e*_{i} is 1 whenever *a*_{i}=1, and whether *a*_{i} is indeed prime (or 1). A deterministic primality test can be performed in polynomial time as was recently shown [59]. Finally, on line 12, we check whether the decomposition is correct. If all tests pass, then the algorithm returns 0,*a*_{1},*a*_{2},…,*a*_{n},*e*_{1},*e*_{2},…,*e*_{n} where *flips* the first input bit. This algorithm and, therefore, the circuit *unique* fixed point 0,*p*_{1},*p*_{2},…,*p*_{m},1^{n−m},*e*_{1},*e*_{2},…,*e*_{m},1^{n−m}, where *p*_{1}>*p*_{2}>⋯>*p*_{m} are primes and

## 5. Conclusion and open questions

The non-causal circuit model describes circuits where the assumption of a *global causal order* is replaced by the assumption of *logical consistency* (i.e. no grandfather antinomy and no uniqueness ambiguity). The problems that are solvable in polynomial time by such circuits form the complexity class P_{NCCirc}. We show that this class equals UP∩coUP, where UP consists of all problems in NP which have an *unambiguous* accepting path. Notable problems within UP∩coUP are integer factorization and parity games. Intuitively, the class P_{NCCirc} contains all search problems that can be solved by determining the *unique* fixed point of a specific reformulation of the problem. This gives a new interpretation of the class UP∩coUP. The *uniqueness* requirement can be understood as arising from the assumption of no *overdetermination* (grandfather antinomy) and of no *underdetermination* (uniqueness ambiguity). Similar complexity classes to FP_{NCCirc} (the functional equivalent of P_{NCCirc}) are FIXP and linear-FIXP=PPAD [62]. Problems within these classes are fixed-point problems where *multiple* fixed points might exist, and in FIXP, the fixed points are allowed to be *irrational*. Finding a Nash equilibrium for two parties is linear-FIXP-complete, and the same problem for three parties or more is FIXP-complete [62]. The class P_{NCCirc}=UP∩coUP is not believed to contain *complete* problems [63].

This result leads us to conclude that classical deterministic CTCs, based on the framework for correlations without global causal order, *cannot* efficiently solve problems outside of UP∩coUP, i.e. P_{LCCTC}⊆P_{NCCirc}. The reason for this is that in the CTC model we require the composed map of the parties with the environment to have a unique fixed point for *any choice* of local operations of the parties. This assumption was dropped when defining the non-causal circuit model. However, note the subtlety that the framework for classical correlations without causal order (as opposed to the classical deterministic CTC model) could, then again, efficiently solve problems not solvable by classical deterministic CTCs. The reason for this is that in the correlations framework, *fine-tuned* process matrices are allowed [38] which are inherently probabilistic—here, we focused on *deterministic* CTCs instead.

When we compare this result to the computational power of the Deutsch CTC model, we note that the CTC model studied here is *dramatically* weaker. This (possibly extreme) drop of computational power could be explained by the assumption of *linearity* which, in contrast to Deutsch’s model, is present in the model studied here. It is known that nonlinearity can lead to astonishing results [64–66]. Put differently, the absence of the grandfather antinomy allows to efficiently solve problems in PSPACE, yet, if we additionally ask for the absence of the uniqueness ambiguity, the computational power drops down to UP∩coUP. In a similar spirit, the Deutsch version of CTCs restricted to *deterministic* fixed points gives a power of at most NP∩coNP [47].

One can put this result in the following perspective: previous results on CTCs show that CTCs are not problematic from a general relativity theory point of view, from a logic point of view, and now we show their relative *innocence* from a computational point of view.

Some of the main open questions that remain are: Does _{NCCirc}, BPP_{LCCTC}) and the quantum (BQP_{NCCirc}, BQP_{LCCTC}) versions of the complexity classes defined here, and how does BQP relate to P_{NCCirc}?

## Data accessibility

This paper has no additional data.

## Authors' contributions

Both authors contributed equally on the results and on the paper. Both authors gave final approval for publication.

## Competing interests

We declare we have no competing interests.

## Funding

This work was supported by the Swiss National Science Foundation (SNF) and the National Centre of Competence in Research ‘Quantum Science and Technology’ (QSIT).

## Acknowledgements

We thank Adarsh Amirtham, Veronika Baumann, Gilles Brassard, Harry Buhrman, Paul Erker, Arne Hansen and Alberto Montina for helpful discussions. We thank Claude Crépeau for his kind invitation to the 2016 Bellairs Workshop, McGill Research Centre, Barbados, where the main ideas emerged. We thank the anonymous referees for helpful comments.

## Footnotes

↵1 The noun ‘paradox’ means a

*seeming*contradiction as opposed to an*actual*contradiction. It originates from the Greek word*paradoxon*which is composed out of*para*(against) and*doxa*(opinion). We use the term*antinomy*for actual contradictions.↵2 The uniqueness ambiguity is also known under the name ‘information paradox’ or ‘information antinomy’.

↵3 It is not the case that the problems are

*concealed*due to*lack of knowledge*[20], but they do not even arise on the*ontic*level. Note that Wallman & Bartlett [20], furthermore, studied Deutsch CTCs where the underlying systems are taken from Spekkens’ [39] ‘toy theory’ of quantum theory.↵4 Some intuition behind this result is that Deutsch CTCs make time

*reusable*just as space is, and thus a polynomial amount of space equals a polynomial amount of*reusable*time [44]. That Deutsch CTCs can solve difficult computational problems efficiently was also pointed out by others (e.g. [45,46]).↵5 We use ∃! to refer to the

*uniqueness*quantifier.

- Received October 6, 2017.
- Accepted November 29, 2017.

- © 2018 The Author(s)

Published by the Royal Society. All rights reserved.