Cover Image

L is different from NP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Montoya, J. Andres
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity F.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Graph-Based Deterministic Polynomial Framwork for NP Problems
by: Lee, Changryeol
Published: (2025)

A Note on the NP-Hardness of PARTITION Via First-Order Projections
by: Iturralde, Paúl Risco
Published: (2025)

Hausdorff Reductions and the Exponential Hierarchies
by: Malizia, Enrico
Published: (2024)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
by: Behera, Amik Raj, et al.
Published: (2026)

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
by: Kühn, Kolja, et al.
Published: (2026)

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
by: Hemaspaandra, Lane A., et al.
Published: (2021)

Disjunctive Complexity
by: Ivanov, Nikita, et al.
Published: (2025)

Understanding Robust Catalytic Computing
by: Koucký, Michal, et al.
Published: (2026)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
by: Kawałek, Piotr, et al.
Published: (2026)

Catalytic Computing and Register Programs Beyond Log-Depth
by: Alekseev, Yaroslav, et al.
Published: (2025)

A point to set principle for finite-state dimension
by: Mayordomo, Elvira
Published: (2022)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
by: Bajaj, Divya, et al.
Published: (2026)

Constructibility and the P versus NP problem
by: Hole, Arne
Published: (2024)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

Structure of sparse Boolean functions over Abelian groups, and its application to testing
by: Chakraborty, Sourav, et al.
Published: (2024)

Explicit Commutative ROABPs from Partial Derivatives
by: Bhargava, Vishwas, et al.
Published: (2024)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

Nonuniform Deterministic Finite Automata over finite algebraic structures
by: Idziak, Paweł M., et al.
Published: (2025)

Imperative process algebra and models of computation
by: Middelburg, C. A.
Published: (2022)

Separating QMA from QCMA with a classical oracle
by: Bostanci, John, et al.
Published: (2025)

Correspondences in computational and dynamical complexity II: forcing complex reductions
by: Everett, Samuel
Published: (2026)

Arithmetic Complexity of Solutions of the Dirichlet Problem
by: Boche, Holger, et al.
Published: (2026)

On the Counting Complexity of the Skolem Problem
by: Jindal, Gorav, et al.
Published: (2024)

Algorithmic hardness of the partition function for nucleic acid strands
by: Ducloz, Gwendal, et al.
Published: (2025)

Realizable Circuit Complexity: Embedding Computation in Space-Time
by: Prada, Benjamin, et al.
Published: (2025)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

SAT problem and Limit of Solomonoff's inductive reasoning theory
by: Pan, Feng
Published: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
by: Anand, Emile, et al.
Published: (2024)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
by: Bodnar, Levente
Published: (2024)

Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)

Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
by: Göös, Mika, et al.
Published: (2025)

A Note on Avoid vs MCSP
by: Hirsch, Edward A., et al.
Published: (2025)

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

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

On Sampling Lower Bounds for Polynomials
by: Khodabandeh, Mohammad Mahdi, et al.
Published: (2026)

Transitions in Dynamic Point Labeling
by: Depian, Thomas, et al.
Published: (2022)