Cover Image

On the Complexity of the Skolem Problem at Low Orders

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bacik, Piotr, Ouaknine, Joël, Worrell, James
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the $p$-adic Skolem Problem
by: Bacik, Piotr, et al.
Published: (2025)

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

On the Subspace Orbit Problem and the Simultaneous Skolem Problem
by: Bacik, Piotr, et al.
Published: (2026)

The 2-Dimensional Constraint Loop Problem is Decidable
by: Guilmant, Quentin, et al.
Published: (2024)

Identity Testing for Radical Expressions
by: Balaji, Nikhil, et al.
Published: (2022)

Multiple Reachability in Linear Dynamical Systems
by: Karimov, Toghrul, et al.
Published: (2024)

On the Descriptive Complexity of Vertex Deletion Problems
by: Bannach, Max, et al.
Published: (2024)

The Descriptive Complexity of Relation Modification Problems
by: Chudigiewitsch, Florian, et al.
Published: (2026)

The Complexity and Expressive Power of Second-Order Extended Logic
by: Feng, Shiguang, et al.
Published: (2022)

The Proof Analysis Problem
by: Arteche, Noel, et al.
Published: (2025)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

Meta-Mathematics of Computational Complexity Theory
by: Oliveira, Igor C.
Published: (2025)

The Monadic Theory of Toric Words
by: Berthé, Valérie, et al.
Published: (2023)

On the Decidability of Presburger Arithmetic Expanded with Powers
by: Karimov, Toghrul, et al.
Published: (2024)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2024)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
by: Atserias, Albert, et al.
Published: (2024)

Singleton algorithms for the Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2025)

Discrete Homotopy and Promise Constraint Satisfaction Problem
by: Beikmohammadi, Arash, et al.
Published: (2025)

On the Decidability of Monadic Theories of Arithmetic Predicates
by: Berthé, Valérie, et al.
Published: (2024)

A Characterization of Basic Feasible Functionals Through Higher-Order Rewriting and Tuple Interpretations
by: Baillot, Patrick, et al.
Published: (2024)

Network Satisfaction Problems Solved by k-Consistency
by: Bodirsky, Manuel, et al.
Published: (2023)

Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
by: Pratt-Hartmann, Ian
Published: (2006)

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
by: Lemke, Caroline, et al.
Published: (2025)

Termination Analysis of Linear-Constraint Programs
by: Ben-Amram, Amir M., et al.
Published: (2025)

Complexity classification of counting graph homomorphisms modulo a prime number
by: Bulatov, Andrei A., et al.
Published: (2021)

Effective Versions of Strong Measure Zero
by: Rayman, Matthew
Published: (2025)

On the consistency of stronger lower bounds for NEXP
by: Thapen, Neil
Published: (2025)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
by: Nechesov, Andrey
Published: (2024)

An order out of nowhere: a new algorithm for infinite-domain CSPs
by: Mottet, Antoine, et al.
Published: (2023)

Proof complexity of positive branching programs
by: Das, Anupam, et al.
Published: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
by: Ježil, Ondřej, et al.
Published: (2026)

The complete classification for quantified equality constraints
by: Zhuk, Dmitriy, et al.
Published: (2021)

Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
by: Meijer, Lucas, et al.
Published: (2025)

Skolemization In Intermediate Logics
by: Baaz, Matthias, et al.
Published: (2025)

Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability
by: Yamakami, Tomoyuki
Published: (2025)

The Constraint Satisfaction Problem Over Multisorted Cores
by: Delic, Dejan, et al.
Published: (2025)

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

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

Set Descriptive Complexity of Solvable Functions
by: Gozzi, Riccardo, et al.
Published: (2024)

On Robustness for the Skolem, Positivity and Ultimate Positivity Problems
by: Akshay, S., et al.
Published: (2022)