Copertina

The Separation of $NP$ and $PSPACE$

Fuente: arXiv

Salvato in:

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

Documenti analoghi

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
di: Lin, Tianrong
Pubblicazione: (2023)

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)

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)

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

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

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)

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

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

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

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

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
di: Ahn, Jungho, et al.
Pubblicazione: (2022)

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

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

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

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

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

The n-vehicle exploration problem is NP-complete
di: Cui, Jinchuan, et al.
Pubblicazione: (2023)

Separation of PSPACE and EXP
di: Czerwinski, Reiner
Pubblicazione: (2021)

Friends-and-strangers is PSPACE-complete
di: Yang, Chao, et al.
Pubblicazione: (2024)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
di: Eua-anant, Pakapim, et al.
Pubblicazione: (2025)

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

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

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
di: Ilmavirta, Joonas, et al.
Pubblicazione: (2023)

Shifted Partial Derivative Polynomial Rank and Codimension
di: Edwards, Darren J.
Pubblicazione: (2025)

Barriers for rectangular matrix multiplication
di: Christandl, Matthias, et al.
Pubblicazione: (2020)

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

Oracle Separations for RPH
di: Hamm, Thekla, et al.
Pubblicazione: (2025)

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

NP-hard problems are not in BQP
di: Czerwinski, Reiner
Pubblicazione: (2023)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
di: Lela, Marko
Pubblicazione: (2025)

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

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

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)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
di: Huseynzade, Rafig
Pubblicazione: (2025)

Quoridor is PSPACE-Complete
di: Drop, Marius, et al.
Pubblicazione: (2026)

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

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