Cover Image

A SAT-based Approach for Specification, Analysis, and Justification of Reductions between NP-complete Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Janičić, Predrag
Format:	Preprint
Published:	2025
Subjects:	Logic in Computer Science F.2; 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)

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

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

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

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

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

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

Formal Verification of COO to CSR Sparse Matrix Conversion (Invited Paper)
by: Appel, Andrew W.
Published: (2025)

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

Complementing an imperative process algebra with a rely/guarantee logic
by: Middelburg, C. A.
Published: (2025)

Probabilistic imperative process algebra
by: Middelburg, C. A.
Published: (2026)

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)

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

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

A Proof-Theoretic Approach to the Semantics of Classical Linear Logic
by: Barroso-Nascimento, Victor, et al.
Published: (2025)

Reasoning about distributive laws in a concurrent refinement algebra
by: Meinicke, Larissa A., et al.
Published: (2024)

Restructuring a concurrent refinement algebra
by: Hayes, Ian J., et al.
Published: (2024)

Dormancy-aware timed branching bisimilarity, with an application to communication protocol analysis
by: Middelburg, C. A.
Published: (2021)

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

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

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

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

Semantics out of context: nominal absolute denotations for first-order logic and computation
by: Gabbay, Murdoch J.
Published: (2013)

One Energy Game for the Spectrum between Branching Bisimilarity and Weak Trace Semantics
by: Bisping, Benjamin, et al.
Published: (2024)

A Quadratic Lower Bound for Simulation
by: Groote, Jan Friso, et al.
Published: (2024)

Do not throw out the baby: Clarithmetics as alternatives to weak arithmetics
by: Japaridze, Giorgi
Published: (2026)

Safety, Relative Tightness and the Probabilistic Frame Rule
by: Jereb, Janez Ignacij, et al.
Published: (2025)

Relation-Algebraic Verification of Disjoint-Set Forests
by: Guttmann, Walter
Published: (2023)

Calculational Design of Hyperlogics by Abstract Interpretation
by: Cousot, Patrick, et al.
Published: (2024)

A Complete Finitary Refinement Type System for Scott-Open Properties
by: Riba, Colin, et al.
Published: (2026)

Chronology as a Consistency Invariant in Composable Information Systems
by: Calvo, Anherutowa, et al.
Published: (2026)

Infinitary Refinement Types for Temporal Properties in Scott Domains
by: Riba, Colin, et al.
Published: (2025)

Branching Bisimilarity for Processes with Time-outs
by: Reghem, Gaspard, et al.
Published: (2024)

Concrete Branching Bisimilarity for Processes with Time-outs
by: Reghem, Gaspard, et al.
Published: (2024)

A propositional cirquent calculus for computability logic
by: Japaridze, Giorgi
Published: (2024)

Satisfiability for Knowing How over Linear Plans is NP-complete
by: Areces, Carlos, et al.
Published: (2026)

Characterizing NC1 with Typed Monoids
by: Dawar, Anuj, et al.
Published: (2025)

A Fibrational Perspective on Differential Linear Logic
by: Koleilat, Jad
Published: (2026)

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