Cover Image

Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hazra, Rishi, Venturato, Gabriele, Martires, Pedro Zuidberg Dos, De Raedt, Luc
Format:	Preprint
Published:	2025
Subjects:	Artificial Intelligence Computational Complexity Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Can Large Language Models Reason? A Characterization via 3-SAT
by: Hazra, Rishi, et al.
Published: (2024)

SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledge
by: Hazra, Rishi, et al.
Published: (2023)

LexiCon: a Benchmark for Planning under Temporal Constraints in Natural Language
by: Mantenoglou, Periklis, et al.
Published: (2025)

Declarative Probabilistic Logic Programming in Discrete-Continuous Domains
by: Martires, Pedro Zuidberg Dos, et al.
Published: (2023)

COvolve: Adversarial Co-Evolution of Large-Language-Model-Generated Policies and Environments via Two-Player Zero-Sum Game
by: Sygkounas, Alkis, et al.
Published: (2026)

REvolve: Reward Evolution with Large Language Models using Human Feedback
by: Hazra, Rishi, et al.
Published: (2024)

Semirings for Probabilistic and Neuro-Symbolic Logic Programming
by: Derkinderen, Vincent, et al.
Published: (2024)

A Quantum Information Theoretic Approach to Tractable Probabilistic Models
by: Martires, Pedro Zuidberg Dos
Published: (2025)

Neurosymbolic Decision Trees
by: Möller, Matthias, et al.
Published: (2025)

Probabilistic Neural Circuits
by: Martires, Pedro Zuidberg Dos
Published: (2024)

Automated Reasoning in Systems Biology: a Necessity for Precision Medicine
by: Martires, Pedro Zuidberg Dos, et al.
Published: (2024)

A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic
by: De Smet, Lennert, et al.
Published: (2024)

Relational Neurosymbolic Markov Models
by: De Smet, Lennert, et al.
Published: (2024)

Independence Is Not an Issue in Neurosymbolic AI
by: Faronius, Håkan Karlsson, et al.
Published: (2025)

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

Two Constraint Compilation Methods for Lifted Planning
by: Mantenoglou, Periklis, et al.
Published: (2025)

NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes
by: Fan, Lizhou, et al.
Published: (2023)

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

KLay: Accelerating Arithmetic Circuits for Neurosymbolic AI
by: Maene, Jaron, et al.
Published: (2024)

Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity
by: Zhan, Yongjian
Published: (2026)

APC-RL: Exceeding Data-Driven Behavior Priors with Adaptive Policy Composition
by: Rietz, Finn, et al.
Published: (2026)

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

SAT Requires Exhaustive Search
by: Xu, Ke, et al.
Published: (2023)

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

Linear Planar 3-SAT and Its Applications in Planning
by: Desbois, Victorien, et al.
Published: (2025)

Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
by: Chen, Bo, et al.
Published: (2025)

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

ActionReasoningBench: Reasoning about Actions with and without Ramification Constraints
by: Handa, Divij, et al.
Published: (2024)

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

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

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

Finding hardness reductions automatically using SAT solvers
by: Bergold, Helena, et al.
Published: (2024)

VERIFY-RL: Verifiable Recursive Decomposition for Reinforcement Learning in Mathematical Reasoning
by: Qasim, Kaleem Ullah, et al.
Published: (2026)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

Nonogram: Complexity of Inference and Phase Transition Behavior
by: Foote, Aaron, et al.
Published: (2025)

Explaining the Ubiquity of Phase Transitions in Decision Problems
by: Jackson, Andrew
Published: (2025)

The Gradient of Algebraic Model Counting
by: Maene, Jaron, et al.
Published: (2025)

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

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

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