Cover Image

A Note on the NP-Hardness of PARTITION Via First-Order Projections

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Iturralde, Paúl Risco
Format:	Preprint
Published:	2025
Subjects:	Logic in Computer Science Computational Complexity F.4.0; F.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

On the Satisfaction Probabilities of $k$-CNF Formulas
by: Tantau, Till
Published: (2022)

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

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

Hereditary First-Order Logic: the tractable quantifier prefix classes
by: Bodirsky, Manuel, et al.
Published: (2024)

Notes on CSPs and Polymorphisms
by: Brady, Zarathustra
Published: (2022)

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

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

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

What If Turing Had Preceded Gödel?
by: Oberhoff, Sebastian
Published: (2024)

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

Hardness of busy beaver value BB(15)
by: Stérin, Tristan, et al.
Published: (2021)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

A Complete Axiomatisation of Equivalence for Discrete Probabilistic Programming
by: Piedeleu, Robin, et al.
Published: (2024)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
by: de Rezende, Susanna F., et al.
Published: (2019)

A proof complexity conjecture and the Incompleteness theorem
by: Krajicek, Jan
Published: (2023)

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)

Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations
by: Kuang, Qipeng, et al.
Published: (2025)

A SAT-based Approach for Specification, Analysis, and Justification of Reductions between NP-complete Problems
by: Janičić, Predrag
Published: (2025)

Universal Algebra in UniMath
by: Amato, Gianluca, et al.
Published: (2020)

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

On the Computational Power of Extensional ESO
by: Bodirsky, Manuel, et al.
Published: (2025)

L is different from NP
by: Montoya, J. Andres
Published: (2024)

A LOCAL View of the Polynomial Hierarchy
by: Reiter, Fabian
Published: (2023)

New Bounds for the Ideal Proof System in Positive Characteristic
by: Behera, Amik Raj, et al.
Published: (2025)

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

Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2025)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
by: Kazakov, Yevgeny, et al.
Published: (2009)

Turing machines deciders, part I
by: The bbchallenge Collaboration, et al.
Published: (2025)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
by: de Rezende, Susanna F., et al.
Published: (2024)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence
by: Kůla, Václav, et al.
Published: (2025)

Complexity of Nonassociative Lambek Calculus with classical logic
by: Płaczek, Paweł
Published: (2024)

Truth Predicate of Inductive Definitions and Logical Complexity of Infinite-Descent Proofs
by: Ito, Sohei, et al.
Published: (2026)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

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

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)