:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Ducros, Vivien, Zandron, Claudio
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2507.01657
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Closure Properties and Characterizations of TotP
by: Ivanashev, Yaroslav
Published: (2025)

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

Some conditions implying if P=NP then P=PSPACE
by: Rodriguez, Ismael
Published: (2026)

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

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

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

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

Colouring $(P_r+P_s)$-Free Graphs
by: Klimošová, Tereza, et al.
Published: (2018)

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)

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

An approximation notion between P and FPTAS
by: Bismuth, Samuel, et al.
Published: (2026)

P-time Algorithms for Typical #EO Problems
by: Meng, Boning, et al.
Published: (2024)

The Complexity of (P3, H)-Arrowing and Beyond
by: Hassan, Zohair Raza
Published: (2024)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
by: Fortnow, Lance
Published: (2025)

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

Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete
by: Bhattacharyya, Arnab, et al.
Published: (2024)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
by: Borzechowski, Michaela, et al.
Published: (2023)

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)

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

#P-hardness proofs of matrix immanants evaluated on restricted matrices
by: Miklos, Istvan, et al.
Published: (2021)

Extensively Not P-Bi-Immune promiseBQP-Complete Languages
by: Jackson, Andrew
Published: (2024)

Bipartite Exact Matching in P
by: Du, Yuefeng
Published: (2026)

Multiplicative weights, equalizers, and P=PPAD
by: Avramopoulos, Ioannis
Published: (2016)

Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
by: Concha-Vega, Pablo
Published: (2026)

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

Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
by: Borzechowski, Michaela, et al.
Published: (2024)

Perfect Zero-Knowledge PCPs for #P
by: Gur, Tom, et al.
Published: (2024)

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)

Intrinsic Sequentiality in P: Causal Limits of Parallel Computation
by: Wei, Jing-Yuan
Published: (2026)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2024)

Constructive Separations and Their Consequences
by: Chen, Lijie, et al.
Published: (2022)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
by: Gaikwad, Ajinkya, et al.
Published: (2025)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

Complexity of Unambiguous Problems in $Σ^P_2$
by: Gilboa, Matan, 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)

Constructive Separations from Gate Elimination
by: Carmosino, Marco, et al.
Published: (2026)

Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces
by: Roy, Diptajit, et al.
Published: (2025)

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

Capturing P: On the Expressive Power and Efficient Evaluation of Boolean Retrieval
by: Aavani, Amir
Published: (2026)

Separations between Combinatorial Measures for Transitive Functions
by: Chakraborty, Sourav, et al.
Published: (2021)