Copertina

Linear Planar 3-SAT and Its Applications in Planning

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Desbois, Victorien, Sankur, Ocan, Schwarzentruber, François
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On Dynamic Programming Theory for Leader-Follower Stochastic Games
di: Dibangoye, Jilles Steeve, et al.
Pubblicazione: (2025)

Verifying Quantized Graph Neural Networks is PSPACE-complete
di: Sälzer, Marco, et al.
Pubblicazione: (2025)

Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete
di: Ghosh, Avijeet, et al.
Pubblicazione: (2025)

Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable
di: Chernobrovkin, Artem, et al.
Pubblicazione: (2025)

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

A Reply to "On Salum's Algorithm for X3SAT"
di: Salum, Latif
Pubblicazione: (2021)

An even simpler hard variant of Not-All-Equal 3-SAT
di: Darmann, Andreas, et al.
Pubblicazione: (2024)

New Results on the Asymptotic Behaviour of a Stochastic SEI Model of Lymphatic Filariasis
di: Ragnimwendé Sawadogo, et al.
Pubblicazione: (2024)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
di: DeJesse, Nicholas, et al.
Pubblicazione: (2025)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
di: He, Yumeng, et al.
Pubblicazione: (2024)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
di: Krokhin, Andrei, et al.
Pubblicazione: (2025)

A Linear Kernel for Planar Vector Domination
di: Sahili, Mahabba El, et al.
Pubblicazione: (2023)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
di: MIT Hardness Group, et al.
Pubblicazione: (2024)

A Graphical #SAT Algorithm for Formulae with Small Clause Density
di: Laakkonen, Tuomas, et al.
Pubblicazione: (2022)

The Value Problem for Multiple-Environment MDPs with Parity Objective
di: Chatterjee, Krishnendu, et al.
Pubblicazione: (2025)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

Geometric Interpretation of 3-SAT and Phase Transition
di: Gillet, Frederic
Pubblicazione: (2025)

A Polynomial Time Algorithm for 3SAT
di: Quigley, Robert
Pubblicazione: (2024)

Geometry Matters in Planar Storyplans
di: Dobler, Alexander, et al.
Pubblicazione: (2025)

Approximately counting maximal independent set is equivalent to #SAT
di: Zhang, Hao, et al.
Pubblicazione: (2024)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)

Ruling Out Low-rank Matrix Multiplication Tensor Decompositions with Symmetries via SAT
di: Yang, Jason
Pubblicazione: (2024)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
di: Han, Zicheng, et al.
Pubblicazione: (2026)

On the Mysteries of MAX NAE-SAT
di: Brakensiek, Joshua, et al.
Pubblicazione: (2020)

Quantum k-SAT Related Hypergraph Problems
di: Kremer, Simon-Luca, et al.
Pubblicazione: (2025)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
di: Bai, Tian, et al.
Pubblicazione: (2026)

On the satisfiability of random $3$-SAT formulas with $k$-wise independent clauses
di: Caragiannis, Ioannis, et al.
Pubblicazione: (2024)

The Parameterized Complexity of Geometric 1-Planarity
di: Firbas, Alexander
Pubblicazione: (2026)

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
di: MIT Hardness Group, et al.
Pubblicazione: (2026)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
di: Hörsch, Florian, et al.
Pubblicazione: (2025)

Further Explanations on "SAT Requires Exhaustive Search"
di: Dong, Qingxiu, et al.
Pubblicazione: (2024)

A Note On The Natural Range Of Unambiguous-SAT
di: Pay, Tayfun
Pubblicazione: (2023)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
di: Cai, Jin-Yi, et al.
Pubblicazione: (2026)

Spiky Rank and Its Applications to Rigidity and Circuits
di: Hambardzumyan, Lianna, et al.
Pubblicazione: (2026)

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
di: Krebs, Andreas, et al.
Pubblicazione: (2025)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
di: Cardoso, Ricardo Rivera, et al.
Pubblicazione: (2025)

Simple Linear Loops: Algebraic Invariants and Applications
di: Manssour, Rida Ait El, et al.
Pubblicazione: (2024)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
di: Austrin, Per, et al.
Pubblicazione: (2024)

Dynamic Planar Graph Isomorphism is in DynFO
di: Datta, Samir, et al.
Pubblicazione: (2026)

SAT, Gadgets, Max2XOR, and Quantum Annealers
di: Ansótegui, Carlos, et al.
Pubblicazione: (2024)