Cover Image

Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Sälzer, Marco, Alsmann, Eric, Lange, Martin
Format:	Preprint
Published:	2024
Subjects:	Logic in Computer Science 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

The Computational Complexity of Satisfiability in State Space Models
by: Alsmann, Eric, et al.
Published: (2025)

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
by: Alsmann, Eric, et al.
Published: (2026)

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

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

The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics
by: Sälzer, Marco, et al.
Published: (2025)

Probabilistic and Causal Satisfiability: Constraining the Model
by: Bläser, Markus, et al.
Published: (2025)

Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees
by: Li, Jinzhao, et al.
Published: (2023)

A Logic for Reasoning About Aggregate-Combine Graph Neural Networks
by: Nunn, Pierre, et al.
Published: (2024)

On Probabilistic and Causal Reasoning with Summation Operators
by: Ibeling, Duligur, et al.
Published: (2024)

A Theory of Formalisms for Representing Knowledge
by: Zhang, Heng, et al.
Published: (2024)

The Descriptive Complexity of Graph Neural Networks
by: Grohe, Martin
Published: (2023)

The Scaling Properties of Implicit Deductive Reasoning in Transformers
by: Vompa, Enrico, et al.
Published: (2026)

Complexity of Faceted Explanations in Propositional Abduction
by: Schmidt, Johannes, et al.
Published: (2025)

Epistemic Skills: Reasoning about Knowledge and Oblivion
by: Liang, Xiaolong, et al.
Published: (2025)

Data Complexity in Expressive Description Logics With Path Expressions
by: Bednarczyk, Bartosz
Published: (2024)

Epistemic Logic Programs: Non-Ground and Counting Complexity
by: Eiter, Thomas, et al.
Published: (2025)

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

Minimal Model Reasoning in Description Logics: Don't Try This at Home!
by: Di Stefano, Federica, et al.
Published: (2025)

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

On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)
by: Artale, Alessandro, et al.
Published: (2025)

On the Expressiveness of State Space Models via Temporal Logics
by: Alsmann, Eric, et al.
Published: (2026)

Advocate for Complete Benchmarks for Formal Reasoning with Formal/Informal Statements and Formal/Informal Proofs
by: Yousefzadeh, Roozbeh, et al.
Published: (2025)

Local vs. Global Interpretability: A Computational Complexity Perspective
by: Bassan, Shahaf, et al.
Published: (2024)

Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory
by: Zubić, Nikola, et al.
Published: (2024)

Formal Mathematical Reasoning: A New Frontier in AI
by: Yang, Kaiyu, et al.
Published: (2024)

Testing for Renamability to Classes of Clause Sets
by: Brandl, Albert, et al.
Published: (2025)

2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
by: Cuteri, Andrea, et al.
Published: (2026)

Reachability In Simple Neural Networks
by: Sälzer, Marco, et al.
Published: (2022)

The Expressive Power of Transformers with Chain of Thought
by: Merrill, William, et al.
Published: (2023)

Rejection in Abstract Argumentation: Harder Than Acceptance?
by: Fichte, Johannes K., et al.
Published: (2024)

Efficient Inference and Computation of Optimal Alternatives for Preference Languages Based On Lexicographic Models
by: Wilson, Nic, et al.
Published: (2024)

Spectra of Cardinality Queries over Description Logic Knowledge Bases
by: Manière, Quentin, et al.
Published: (2024)

Compilation and Fast Model Counting beyond CNF
by: de Colnet, Alexis, et al.
Published: (2025)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
by: Amir, Guy, et al.
Published: (2024)

Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks
by: Khalife, Sammy, et al.
Published: (2024)

On the Computational Tractability of the (Many) Shapley Values
by: Marzouk, Reda, et al.
Published: (2025)

Provably Explaining Neural Additive Models
by: Bassan, Shahaf, et al.
Published: (2026)

What makes an Ensemble (Un) Interpretable?
by: Bassan, Shahaf, et al.
Published: (2025)

FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond Competitive Programming
by: Beniamini, Gal, et al.
Published: (2025)

Conditional Logical Message Passing Transformer for Complex Query Answering
by: Zhang, Chongzhi, et al.
Published: (2024)