Copertina

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Lin, Tianrong
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Computational Complexity Probability 68Q01, 68Q10, 68Q15, 68Q17
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

The Separation of $NP$ and $PSPACE$
di: Lin, Tianrong
Pubblicazione: (2021)

Polynomial Identity Testing via Evaluation of Rational Functions
di: Hu, Ivan, et al.
Pubblicazione: (2022)

Resolution of The Linear-Bounded Automata Question
di: Lin, Tianrong
Pubblicazione: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
di: Lin, Tianrong
Pubblicazione: (2021)

P not equal to NP
di: Delgado, Daniel Cardona
Pubblicazione: (2023)

Unifying lower bounds for algebraic machines, semantically
di: Seiller, Thomas, et al.
Pubblicazione: (2018)

Beyond the Existential Theory of the Reals
di: Schaefer, Marcus, et al.
Pubblicazione: (2022)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
di: Edwards, Darren J.
Pubblicazione: (2025)

Some derivations among Logarithmic Space Bounded Counting Classes
di: Janaki, V., et al.
Pubblicazione: (2023)

The Complexity of Iterated Reversible Computation
di: Eppstein, David
Pubblicazione: (2021)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
di: Abdullah, Duaa, et al.
Pubblicazione: (2025)

Completeness classes in algebraic complexity theory
di: Bürgisser, Peter
Pubblicazione: (2024)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
di: Shalunov, Yakov
Pubblicazione: (2023)

Weighted Automata and Logics Meet Computational Complexity
di: Kostolányi, Peter
Pubblicazione: (2023)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
di: Bergougnoux, Benjamin, et al.
Pubblicazione: (2025)

Undefinability of Approximation of 2-to-2 Games
di: Dawar, Anuj, et al.
Pubblicazione: (2025)

Fully Characterizing Lossy Catalytic Computation
di: Folkertsma, Marten, et al.
Pubblicazione: (2024)

Generalisations of Matrix Partitions : Complexity and Obstructions
di: Barsukov, Alexey, et al.
Pubblicazione: (2021)

Computational Complexity of Determining the Assembly Index
di: Masierak, Piotr
Pubblicazione: (2026)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
di: Li, Zhangsong
Pubblicazione: (2026)

Teaching and Learning under Deductive Errors
di: Telle, Jan Arne, et al.
Pubblicazione: (2026)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
di: Böhnlein, Toni, et al.
Pubblicazione: (2024)

Recent Advances in Debordering Methods
di: Dutta, Pranjal, et al.
Pubblicazione: (2025)

Quantum Lower Bounds by Sample-to-Query Lifting
di: Wang, Qisheng, et al.
Pubblicazione: (2023)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
di: Meir, Or
Pubblicazione: (2023)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
di: Tzameret, Iddo, et al.
Pubblicazione: (2023)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
di: Lin, Tianrong
Pubblicazione: (2024)

Computational Complexity of Model-Checking Quantum Pushdown Systems
di: Lin, Deren, et al.
Pubblicazione: (2025)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
di: Marković, Petar, et al.
Pubblicazione: (2026)

CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
di: Zhang, Weikun K., et al.
Pubblicazione: (2026)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
di: Li, Zhangsong
Pubblicazione: (2025)

The Algorithmic Phase Transition in Correlated Spiked Models
di: Li, Zhangsong
Pubblicazione: (2025)

Analysis of multivariate symbol statistics in primitive rational models
di: Goldwurm, Massimiliano, et al.
Pubblicazione: (2026)

A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis
di: Petrov, Petar P.
Pubblicazione: (2022)

Cluster Vertex Deletion Problems on Cubic Graphs
di: Rusu, Irena
Pubblicazione: (2025)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
di: Avila, Tatiana Rocha, et al.
Pubblicazione: (2026)

Languages given by Finite Automata over the Unary Alphabet
di: Czerwiński, Wojciech, et al.
Pubblicazione: (2023)

Algorithms for Minimum Membership Dominating Set Problem
di: Reddy, Sangam Balchandar, et al.
Pubblicazione: (2024)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
di: Ye, Lixi
Pubblicazione: (2026)

Looking for all solutions of the Max Atom Problem (MAP)
di: Truffet, Laurent
Pubblicazione: (2024)