Copertina

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Lagerkvist, Victor, Groven, Johanna, Eriksson, Leif
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity 68R07, 68Q27, 90C39, 68Q17 F.2.2; I.2.4
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Approaching I/O-optimality for Approximate Attention
di: Papp, Pál András, et al.
Pubblicazione: (2026)

The n-vehicle exploration problem is NP-complete
di: Cui, Jinchuan, et al.
Pubblicazione: (2023)

A polynomial-time algorithm for deciding the Hilbert Nullstellensatz over $\mathbb{Z}_2$. A proof of $\mathbf{P}=\mathbf{NP}$ hypothesis
di: Petrov, Petar P.
Pubblicazione: (2022)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
di: Bergougnoux, Benjamin, et al.
Pubblicazione: (2025)

Completeness classes in algebraic complexity theory
di: Bürgisser, Peter
Pubblicazione: (2024)

Computational Complexity of Determining the Assembly Index
di: Masierak, Piotr
Pubblicazione: (2026)

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

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
di: Abdullah, Duaa, et al.
Pubblicazione: (2025)

Teaching and Learning under Deductive Errors
di: Telle, Jan Arne, et al.
Pubblicazione: (2026)

On weighted graph separation problems and flow-augmentation
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)

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

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

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

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

Polynomial Identity Testing via Evaluation of Rational Functions
di: Hu, Ivan, et al.
Pubblicazione: (2022)

DAG Scheduling in the BSP Model
di: Papp, Pál András, et al.
Pubblicazione: (2023)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
di: Chen, Yijia, et al.
Pubblicazione: (2023)

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

The Optimizer Quotient and the Certification Trilemma
di: Simas, Tristan
Pubblicazione: (2026)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
di: Lin, Tianrong
Pubblicazione: (2023)

Abductive explanations of classifiers under constraints: Complexity and properties
di: Cooper, Martin, et al.
Pubblicazione: (2024)

The Separation of $NP$ and $PSPACE$
di: Lin, Tianrong
Pubblicazione: (2021)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
di: Ye, Lixi
Pubblicazione: (2026)

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

P not equal to NP
di: Delgado, Daniel Cardona
Pubblicazione: (2023)

Folding One Polyhedral Metric Graph into Another
di: Chung, Lily, et al.
Pubblicazione: (2024)

Algorithms for Minimum Membership Dominating Set Problem
di: Reddy, Sangam Balchandar, et al.
Pubblicazione: (2024)

Unifying lower bounds for algebraic machines, semantically
di: Seiller, Thomas, et al.
Pubblicazione: (2018)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
di: Edwards, Darren J.
Pubblicazione: (2025)

Modularity in Transformers: Investigating Neuron Separability & Specialization
di: Pochinkov, Nicholas, et al.
Pubblicazione: (2024)

Think Thrice Before You Speak: Dual knowledge-enhanced Theory-of-Mind Reasoning for Persuasive Agents
di: Ma, Minghui, et al.
Pubblicazione: (2026)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
di: Meir, Or
Pubblicazione: (2023)

Undefinability of Approximation of 2-to-2 Games
di: Dawar, Anuj, et al.
Pubblicazione: (2025)

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

UR4NNV: Neural Network Verification, Under-approximation Reachability Works!
di: Liang, Zhen, et al.
Pubblicazione: (2024)

Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms
di: Kratsios, Anastasis, et al.
Pubblicazione: (2025)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
di: Jansen, Klaus, et al.
Pubblicazione: (2024)

Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases
di: Emmerich, Michael T. M.
Pubblicazione: (2026)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
di: Demaine, Erik D., et al.
Pubblicazione: (2024)

Shifted Partial Derivative Polynomial Rank and Codimension
di: Edwards, Darren J.
Pubblicazione: (2025)