Cover Image

Some conditions implying if P=NP then P=PSPACE

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Rodriguez, Ismael
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Proofs of NP = coNP = PSPACE: Current upgrade
by: Gordeev, Lev, et al.
Published: (2023)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$
by: Dingel, David, et al.
Published: (2024)

P=NP
by: Deng, Zikang
Published: (2024)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
by: Chavrimootoo, Michael C., et al.
Published: (2026)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
by: Grüne, Christoph, et al.
Published: (2026)

P vs. NP
by: Uribe, Daniel
Published: (2016)

On P Versus NP
by: Gordeev, Lev
Published: (2020)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

A Critique of Deng's "P=NP"
by: Humphreys, Isabel, et al.
Published: (2025)

Topological Collapse: P = NP Implies #P = FP via Solution-Space Homology
by: Alasli, M.
Published: (2026)

The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO
by: Meng, Boning, et al.
Published: (2025)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
by: Çivril, Ali
Published: (2021)

A proof of P!=NP
by: McCallum, Rupert
Published: (2020)

Atropos-k is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
by: MIT Hardness Group, et al.
Published: (2024)

An Intrinsic Barrier for Resolving P = NP (2-SAT as Flat, 3-SAT as High-Dimensional Void-Rich)
by: Alasli, M.
Published: (2025)

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
by: DeStefano, Zachary, et al.
Published: (2025)

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
by: MIT Hardness Group, et al.
Published: (2025)

Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$
by: Çivril, Ali
Published: (2021)

There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: $P \not= NP$
by: Kayibi, Koko-Kalambay Kalafan
Published: (2018)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
by: Mitosek, Piotr
Published: (2024)

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
by: Ani, Hayashi, et al.
Published: (2024)

Maker-Maker games of rank 4 are PSPACE-complete
by: Galliot, Florian, et al.
Published: (2025)

A Simple Proof that Ricochet Robots is PSPACE-Complete
by: Balanza-Martinez, Jose, et al.
Published: (2024)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)

Nondango is NP-Complete
by: Ruangwises, Suthee
Published: (2023)

Verifying Quantized Graph Neural Networks is PSPACE-complete
by: Sälzer, Marco, et al.
Published: (2025)

On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
by: DeJesse, Nicholas, et al.
Published: (2025)

BusOut is NP-complete
by: Ishibashi, Takehiro, et al.
Published: (2025)

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

On Kernelization with Access to NP-Oracles
by: Molter, Hendrik, et al.
Published: (2025)

A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
by: Ming, Gao
Published: (2022)

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
by: MIT Gadgets Group, et al.
Published: (2020)

4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete
by: Galliot, Florian
Published: (2025)

A Quantale-Weakness Route to $P \neq NP$ via CD Evidence Normalization and Gauge-Buffered Locked Ensembles
by: Goertzel, Ben
Published: (2025)

NP-Completeness of Neighborhood Balanced Colorings
by: Asaeedi, Saeed
Published: (2024)

The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)