Computational tameness of classical non-causal models.

We show that the computational power of the non-causal circuit model, i.e. the circuit model where the assumption of a is replaced by the assumption of , 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 of that class. Thus, in stark contrast to other CTC models, these CTCs efficiently solve NP-complete problems, unless NP=UP∩coUP=coNP, which lets their existence in nature appear . This result gives a new characterization of UP∩coUP in terms of fixed points.