Copertina

Graph-Based Deterministic Polynomial Framwork for NP Problems

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Lee, Changryeol
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity F.1.3; F.2.0
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Constructibility and the P versus NP problem
di: Hole, Arne
Pubblicazione: (2024)

Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework
di: Lee, Changryeol
Pubblicazione: (2026)

PosSLP and Sum of Squares
di: Bläser, Markus, et al.
Pubblicazione: (2024)

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

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

I/O complexity and pebble games with partial computations
di: Sobczyk, Aleksandros
Pubblicazione: (2024)

L is different from NP
di: Montoya, J. Andres
Pubblicazione: (2024)

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

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

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
di: Hakoniemi, Tuomas, et al.
Pubblicazione: (2024)

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

On the Complexity of Determinations
di: Hellerstein, Joseph M.
Pubblicazione: (2026)

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

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

On the Decidability of Verification under Release/Acquire
di: Conrado, Giovanna Kobus, et al.
Pubblicazione: (2026)

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

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

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

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

On bounded depth proofs for Tseitin formulas on the grid; revisited
di: Håstad, Johan, et al.
Pubblicazione: (2022)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

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

Supercritical Tradeoffs for Monotone Circuits
di: Göös, Mika, et al.
Pubblicazione: (2024)

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

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

Structure-Guided Automated Reasoning
di: Bannach, Max, et al.
Pubblicazione: (2023)

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

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

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
di: Anand, Emile
Pubblicazione: (2025)

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

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

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

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

Failure of the strong feasible disjunction property
di: Krajicek, Jan
Pubblicazione: (2026)

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

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

Shifted Partial Derivative Polynomial Rank and Codimension
di: Edwards, Darren J.
Pubblicazione: (2025)

Disjunctive Complexity
di: Ivanov, Nikita, et al.
Pubblicazione: (2025)

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