Computational tameness of classical non-causal models

DOI10.1098/rspa.2017.0698zbMath1402.81082arXiv1611.05641OpenAlexW2550835866WikidataQ51557579 ScholiaQ51557579MaRDI QIDQ4556871

Ämin Baumeler, Stefan Wolf

Publication date: 28 November 2018

Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.05641

zbMATH Keywords

causalitycomplexity theoryclosed timelike curvesnon-causal computationunambiguous polynomial time

Mathematics Subject Classification ID

Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Physical Computational Complexity and First-order Logic, Reversible time travel with freedom of choice

Cites Work

• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Time travel: Deutsch vs. teleportation
• Revisiting consistency conditions for quantum states of systems on closed timelike curves: an epistemic perspective
• On total functions, existence theorems and computational complexity
• Self-witnessing polynomial-time complexity and prime factorization
• Relative complexity of checking and evaluating
• The polynomial-time hierarchy
• PRIMES is in P
• One-way permutations and self-witnessing languages
• Quantum computation with programmable connections between gates
• Quantum theory: informational foundations and foils
• On the Complexity of Nash Equilibria and Other Fixed Points
• Closed timelike curves make quantum and classical computing equivalent
• Gravitational Field of a Spinning Mass as an Example of Algebraically Special Metrics
• Threshold Computation and Cryptographic Security
• Weinberg’s nonlinear quantum mechanics and the Einstein-Podolsky-Rosen paradox
• Computational Complexity
• Quantum computing, postselection, and probabilistic polynomial-time
• An Example of a New Type of Cosmological Solutions of Einstein's Field Equations of Gravitation
• The simplest causal inequalities and their violation
• The space of logically consistent classical processes without causal order
• Exact Space-Times in Einstein's General Relativity
• Empty space-times admitting a three parameter group of motions