Image de couverture de livre

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

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Lin, Tianrong
Format:	Preprint
Publié:	2023
Sujets:	Computational Complexity Probability 68Q01, 68Q10, 68Q15, 68Q17
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

The Separation of $NP$ and $PSPACE$
par: Lin, Tianrong
Publié: (2021)

Polynomial Identity Testing via Evaluation of Rational Functions
par: Hu, Ivan, et autres
Publié: (2022)

Resolution of The Linear-Bounded Automata Question
par: Lin, Tianrong
Publié: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
par: Lin, Tianrong
Publié: (2021)

P not equal to NP
par: Delgado, Daniel Cardona
Publié: (2023)

Unifying lower bounds for algebraic machines, semantically
par: Seiller, Thomas, et autres
Publié: (2018)

Beyond the Existential Theory of the Reals
par: Schaefer, Marcus, et autres
Publié: (2022)

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

Some derivations among Logarithmic Space Bounded Counting Classes
par: Janaki, V., et autres
Publié: (2023)

The Complexity of Iterated Reversible Computation
par: Eppstein, David
Publié: (2021)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
par: Abdullah, Duaa, et autres
Publié: (2025)

Completeness classes in algebraic complexity theory
par: Bürgisser, Peter
Publié: (2024)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
par: Shalunov, Yakov
Publié: (2023)

Weighted Automata and Logics Meet Computational Complexity
par: Kostolányi, Peter
Publié: (2023)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

Undefinability of Approximation of 2-to-2 Games
par: Dawar, Anuj, et autres
Publié: (2025)

Fully Characterizing Lossy Catalytic Computation
par: Folkertsma, Marten, et autres
Publié: (2024)

Generalisations of Matrix Partitions : Complexity and Obstructions
par: Barsukov, Alexey, et autres
Publié: (2021)

Computational Complexity of Determining the Assembly Index
par: Masierak, Piotr
Publié: (2026)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
par: Li, Zhangsong
Publié: (2026)

Teaching and Learning under Deductive Errors
par: Telle, Jan Arne, et autres
Publié: (2026)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
par: Böhnlein, Toni, et autres
Publié: (2024)

Recent Advances in Debordering Methods
par: Dutta, Pranjal, et autres
Publié: (2025)

Quantum Lower Bounds by Sample-to-Query Lifting
par: Wang, Qisheng, et autres
Publié: (2023)

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

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
par: Tzameret, Iddo, et autres
Publié: (2023)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
par: Lin, Tianrong
Publié: (2024)

Computational Complexity of Model-Checking Quantum Pushdown Systems
par: Lin, Deren, et autres
Publié: (2025)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
par: Marković, Petar, et autres
Publié: (2026)

CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
par: Zhang, Weikun K., et autres
Publié: (2026)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
par: Li, Zhangsong
Publié: (2025)

The Algorithmic Phase Transition in Correlated Spiked Models
par: Li, Zhangsong
Publié: (2025)

Analysis of multivariate symbol statistics in primitive rational models
par: Goldwurm, Massimiliano, et autres
Publié: (2026)

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

Cluster Vertex Deletion Problems on Cubic Graphs
par: Rusu, Irena
Publié: (2025)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
par: Avila, Tatiana Rocha, et autres
Publié: (2026)

Languages given by Finite Automata over the Unary Alphabet
par: Czerwiński, Wojciech, et autres
Publié: (2023)

Algorithms for Minimum Membership Dominating Set Problem
par: Reddy, Sangam Balchandar, et autres
Publié: (2024)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
par: Ye, Lixi
Publié: (2026)

Looking for all solutions of the Max Atom Problem (MAP)
par: Truffet, Laurent
Publié: (2024)