Copertina

A point to set principle for finite-state dimension

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Mayordomo, Elvira
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Computational Complexity F.1.3; F.1.1
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

$\rm P$ has polynomial-time finite-state verifiers
di: Gezer, M. Utkan, et al.
Pubblicazione: (2023)

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

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

Regular Model Checking for Systems with Effectively Regular Reachability Relation
di: Esparza, Javier, et al.
Pubblicazione: (2025)

Stochastic well-structured transition systems
di: Aspnes, James
Pubblicazione: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
di: Idziak, Paweł M., et al.
Pubblicazione: (2025)

Graph Neural Networks and Arithmetic Circuits
di: Barlag, Timon, et al.
Pubblicazione: (2024)

Functional Closure Properties of Finite $\mathbb{N}$-weighted Automata
di: Dörfler, Julian, et al.
Pubblicazione: (2024)

Average Attention Transformers and Arithmetic Circuits
di: Ehrmuth, Lena, et al.
Pubblicazione: (2026)

Recurrent Graph Neural Networks and Arithmetic Circuits
di: Barlag, Timon, et al.
Pubblicazione: (2026)

L is different from NP
di: Montoya, J. Andres
Pubblicazione: (2024)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
di: Behera, Amik Raj, et al.
Pubblicazione: (2026)

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

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

Disjunctive Complexity
di: Ivanov, Nikita, et al.
Pubblicazione: (2025)

Hausdorff Reductions and the Exponential Hierarchies
di: Malizia, Enrico
Pubblicazione: (2024)

Understanding Robust Catalytic Computing
di: Koucký, Michal, et al.
Pubblicazione: (2026)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
di: Antonelli, Melissa, et al.
Pubblicazione: (2025)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
di: Kawałek, Piotr, et al.
Pubblicazione: (2026)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
di: Anand, Emile, et al.
Pubblicazione: (2024)

Algorithmic hardness of the partition function for nucleic acid strands
di: Ducloz, Gwendal, et al.
Pubblicazione: (2025)

Realizable Circuit Complexity: Embedding Computation in Space-Time
di: Prada, Benjamin, et al.
Pubblicazione: (2025)

On the Complexity of Determinations
di: Hellerstein, Joseph M.
Pubblicazione: (2026)

Graph-Based Deterministic Polynomial Framwork for NP Problems
di: Lee, Changryeol
Pubblicazione: (2025)

Structure of sparse Boolean functions over Abelian groups, and its application to testing
di: Chakraborty, Sourav, et al.
Pubblicazione: (2024)

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

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

On bounded depth proofs for Tseitin formulas on the grid; revisited
di: Håstad, Johan, et al.
Pubblicazione: (2022)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
di: Conneryd, Jonas, et al.
Pubblicazione: (2025)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
di: de Rezende, Susanna F., et al.
Pubblicazione: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
di: de Rezende, Susanna F., et al.
Pubblicazione: (2024)

Supercritical Tradeoffs for Monotone Circuits
di: Göös, Mika, et al.
Pubblicazione: (2024)

A LOCAL View of the Polynomial Hierarchy
di: Reiter, Fabian
Pubblicazione: (2023)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
di: Conneryd, Jonas, et al.
Pubblicazione: (2025)

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