Imagen de Portada

Computational Complexity of Determining the Assembly Index

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Masierak, Piotr
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity 68Q17 (Primary) 68Q45, 68R15 (Secondary) F.2.2; F.4.3; E.4
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
por: Dorochko, Leonid, et al.
Publicado: (2026)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
por: Saffidine, Abdallah, et al.
Publicado: (2025)

Languages of Words of Low Automatic Complexity Are Hard to Compute
por: Chen, Joey, et al.
Publicado: (2025)

Topological Logics with Connectedness over Euclidean Spaces
por: Kontchakov, Roman, et al.
Publicado: (2011)

A Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes
por: Bruse, Florian, et al.
Publicado: (2026)

Around Context-Free Grammars -- a Normal Form, a Representation Theorem, and a Regular Approximation
por: Cojocaru, Liliana
Publicado: (2015)

Templated Assembly Theory: An Extension of the Canonical Assembly Index with Block-Compressed Template
por: Masierak, Piotr
Publicado: (2026)

Grammar-Constrained (CFL) Reachability: Subcubic Preprocessing, Indexing Trade-offs, and Structured Decoding Semantics
por: Alpay, Faruk, et al.
Publicado: (2026)

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

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
por: Lagerkvist, Victor, et al.
Publicado: (2026)

Jump Complexity of Deterministic Finite Automata with Translucent Letters
por: Fazekas, Szilárd Zsolt, et al.
Publicado: (2025)

On Graph Grammars and Games
por: Vijayakumar, Jayakrishna, et al.
Publicado: (2024)

The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory
por: Peyrichou, Romain
Publicado: (2026)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
por: Lela, Marko
Publicado: (2025)

A Formalization of Co-Transcriptional Splicing as an Operation on Formal Languages
por: Cho, Da-Jung, et al.
Publicado: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
por: Kelley, Zander, et al.
Publicado: (2023)

Computing the Bandwidth of Meager Timed Automata
por: Asarin, Eugene, et al.
Publicado: (2024)

Disproving Termination of Non-Erasing Sole Combinatory Calculus with Tree Automata (Full Version)
por: Nakano, Keisuke, et al.
Publicado: (2024)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
por: Lela, Marko
Publicado: (2025)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
por: Huseynzade, Rafig
Publicado: (2025)

Completeness classes in algebraic complexity theory
por: Bürgisser, Peter
Publicado: (2024)

Anti-Context-Free languages
por: Cardó, Carles
Publicado: (2024)

Hive is PSPACE-Hard
por: Andel, Daniël, et al.
Publicado: (2025)

Weighing Obese Timed Languages
por: Asarin, Eugene, et al.
Publicado: (2025)

Greedy Poisson Rejection Sampling
por: Flamich, Gergely
Publicado: (2023)

On Small-depth Frege Proofs for PHP
por: Håstad, Johan
Publicado: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
por: Levin, Leonid A.
Publicado: (2022)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
por: Eua-anant, Pakapim, et al.
Publicado: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
por: Lela, Marko
Publicado: (2025)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
por: Shalunov, Yakov
Publicado: (2023)

Well-Quasi-Orderings on Word Languages
por: Lhote, Nathan, et al.
Publicado: (2025)

Emulation-Completeness of Programming Languages
por: Morse, Gregory, et al.
Publicado: (2026)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
por: Böhnlein, Toni, et al.
Publicado: (2024)

Recursive windows for grammar logics of bounded density
por: Gasquet, Olivier
Publicado: (2025)

PSPACE-completeness of bimodal transitive weak-density logic
por: Balbiani, Philippe, et al.
Publicado: (2025)

The Word Problem for Finitary Automaton Groups
por: Kotowsky, Maximilian, et al.
Publicado: (2023)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
por: Philip, Geevarghese, et al.
Publicado: (2026)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
por: Grochow, Joshua A., et al.
Publicado: (2021)

Propositional dynamic logic and asynchronous cascade decompositions for regular trace languages
por: Adsul, Bharat, et al.
Publicado: (2024)

Subsequence Matching and Analysis Problems for Formal Languages
por: Fazekas, Szilárd Zsolt, et al.
Publicado: (2024)