Image de couverture de livre

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines

Fuente: arXiv

Enregistré dans:

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

Documents similaires

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

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

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
par: Huseynzade, Rafig
Publié: (2025)

From Gödel incompleteness to the consistency of circuit lower bounds
par: Atserias, Albert, et autres
Publié: (2026)

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

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

Extended Nullstellensatz proof systems
par: Krajicek, Jan
Publié: (2023)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
par: Lin, Tianrong
Publié: (2023)

NP-hard problems are not in BQP
par: Czerwinski, Reiner
Publié: (2023)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
par: Lela, Marko
Publié: (2025)

The Polynomial Hierarchy does not collapse
par: Czerwinski, Reiner
Publié: (2024)

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

Separation of PSPACE and EXP
par: Czerwinski, Reiner
Publié: (2021)

The Optimizer Quotient and the Certification Trilemma
par: Simas, Tristan
Publié: (2026)

Adversarial Barrier in Uniform Class Separation
par: Rosko, Milan
Publié: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
par: Hakoniemi, Tuomas, et autres
Publié: (2024)

Evolomino is NP-complete
par: Nikolaev, Andrei V.
Publié: (2025)

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

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

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
par: Schewe, Klaus-Dieter
Publié: (2020)

The Algebra of Nondeterministic Finite Automata
par: Gorrieri, Roberto
Publié: (2023)

Complexities of Well-Quasi-Ordered Substructural Logics
par: Galatos, Nikolaos, et autres
Publié: (2025)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
par: Diakonikolas, Ilias, et autres
Publié: (2024)

Counting Martingales for Measure and Dimension in Complexity Classes
par: Hitchcock, John M., et autres
Publié: (2025)

Shifted Partial Derivative Polynomial Rank and Codimension
par: Edwards, Darren J.
Publié: (2025)

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

The Solver's Paradox in Formal Problem Spaces
par: Rosko, Milan
Publié: (2025)

A Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes
par: Bruse, Florian, et autres
Publié: (2026)

Locality, Consistency, and the Tractability Frontier
par: Simas, Tristan
Publié: (2026)

On the existence of strong proof complexity generators
par: Krajicek, Jan
Publié: (2022)

A Minimal Substitution Basis for the Kalmár Elementary Functions
par: Prunescu, Mihai, et autres
Publié: (2025)

Choiceless Polynomial Space
par: Ferrarotti, Flavio, et autres
Publié: (2024)

Meta Theorem for Hardness on FCP-Problem
par: Nagao, Atsuki, et autres
Publié: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
par: Hirsch, Edward A., et autres
Publié: (2025)

Linear Matroid Intersection is in Catalytic Logspace
par: Agarwala, Aryan, et autres
Publié: (2025)

Oracle Separations for RPH
par: Hamm, Thekla, et autres
Publié: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
par: Göös, Mika, et autres
Publié: (2025)

A Note on Avoid vs MCSP
par: Hirsch, Edward A., et autres
Publié: (2025)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
par: Garcia, Baruch
Publié: (2026)

A Logspace Constructive Proof of L=SL
par: Buss, Sam, et autres
Publié: (2025)