Cover Image

On the Counting Complexity of the Skolem Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jindal, Gorav, Ouaknine, Joël
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Logic in Computer Science F.1.3; F.1.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
by: Bläser, Markus, et al.
Published: (2025)

SAT problem and Limit of Solomonoff's inductive reasoning theory
by: Pan, Feng
Published: (2025)

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

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

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

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

Turing machines deciders, part I
by: The bbchallenge Collaboration, et al.
Published: (2025)

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

Hardness of busy beaver value BB(15)
by: Stérin, Tristan, et al.
Published: (2021)

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

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

On the Complexity of the Conditional Independence Implication Problem With Bounded Cardinalities
by: Makowski, Michał
Published: (2024)

Homogeneous Algebraic Complexity Theory and Algebraic Formulas
by: Dutta, Pranjal, et al.
Published: (2023)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

Explicit Commutative ROABPs from Partial Derivatives
by: Bhargava, Vishwas, et al.
Published: (2024)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

A LOCAL View of the Polynomial Hierarchy
by: Reiter, Fabian
Published: (2023)

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

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

A SAT-based Approach for Specification, Analysis, and Justification of Reductions between NP-complete Problems
by: Janičić, Predrag
Published: (2025)

Tight bounds on depth-2 QAC-circuits computing parity
by: Fenner, Stephen, et al.
Published: (2025)

Fixed-parameter debordering of Waring rank
by: Dutta, Pranjal, et al.
Published: (2024)

How to Verify a Turing Machine with Dafny
by: Lederer, Edgar F. A.
Published: (2026)

Disjunctive Complexity
by: Ivanov, Nikita, et al.
Published: (2025)

Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)

On the formalization of the notion of a concurrent algorithm
by: Middelburg, C. A.
Published: (2024)

Formalizing the notions of non-interactive and interactive algorithms
by: Middelburg, C. A.
Published: (2024)

On the formalization of the notion of an algorithm
by: Middelburg, C. A.
Published: (2024)

Constructibility and the P versus NP problem
by: Hole, Arne
Published: (2024)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

Notes on CSPs and Polymorphisms
by: Brady, Zarathustra
Published: (2022)

Complex Algebras of Arithmetic
by: Düntsch, Ivo, et al.
Published: (2009)

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
by: Kühn, Kolja, et al.
Published: (2026)

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
by: Hemaspaandra, Lane A., et al.
Published: (2021)

On the Reachability Problem for One-Dimensional Thin Grammar Vector Addition Systems
by: Xue, Chengfeng, et al.
Published: (2026)

On the Complexity of the Skolem Problem at Low Orders
by: Bacik, Piotr, et al.
Published: (2025)

On Some Complexity Results for Even Linear Languages
by: Cojocaru, Liliana
Published: (2024)