Buchumschlag

Locality, Consistency, and the Tractability Frontier

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Simas, Tristan
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity Artificial Intelligence Logic in Computer Science 90C31, 68Q15, 03D20, 68T20 F.2.2; F.4.1; I.2.4
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Optimizer Quotient and the Certification Trilemma
von: Simas, Tristan
Veröffentlicht: (2026)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
von: Grochow, Joshua A., et al.
Veröffentlicht: (2022)

Adversarial Barrier in Uniform Class Separation
von: Rosko, Milan
Veröffentlicht: (2025)

Extended Nullstellensatz proof systems
von: Krajicek, Jan
Veröffentlicht: (2023)

Mechanised uniform interpolation for modal logics K, GL, and iSL
von: Férée, Hugo, et al.
Veröffentlicht: (2024)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2023)

Complexities of Well-Quasi-Ordered Substructural Logics
von: Galatos, Nikolaos, et al.
Veröffentlicht: (2025)

Topological Logics with Connectedness over Euclidean Spaces
von: Kontchakov, Roman, et al.
Veröffentlicht: (2011)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
von: Grochow, Joshua A., et al.
Veröffentlicht: (2021)

Count-Free Weisfeiler--Leman and Group Isomorphism
von: Collins, Nathaniel A., et al.
Veröffentlicht: (2022)

Combining Mechanical and Agentic Specification Inference for Move
von: Grieskamp, Wolfgang, et al.
Veröffentlicht: (2026)

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

Understanding and Improving Automated Proof Synthesis for Interactive Theorem Provers
von: Zhang, Manqing, et al.
Veröffentlicht: (2026)

A correspondence between the time and space complexity
von: Latkin, Ivan V.
Veröffentlicht: (2023)

Proof-Carrying Certificates for LLM Pipelines: A Trust-Boundary Architecture
von: Koomullil, George
Veröffentlicht: (2026)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
von: Saffidine, Abdallah, et al.
Veröffentlicht: (2025)

Classification of Covering Spaces and Canonical Change of Basepoint
von: Wemmenhove, Jelle, et al.
Veröffentlicht: (2024)

On the existence of strong proof complexity generators
von: Krajicek, Jan
Veröffentlicht: (2022)

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

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2024)

Normative Conditional Reasoning as a Fragment of HOL
von: Parent, Xavier, et al.
Veröffentlicht: (2023)

Computational Complexity of Physical Counting
von: Simas, Tristan
Veröffentlicht: (2026)

Determination of the fifth Busy Beaver value
von: The bbchallenge Collaboration, et al.
Veröffentlicht: (2025)

Monoid Theory in Alonzo: A Little Theories Formalization in Simple Type Theory
von: Farmer, William M., et al.
Veröffentlicht: (2023)

Computing Non-Repetitive Sequences with a Computable Lefthanded Local Lemma
von: Mourad, Daniel
Veröffentlicht: (2024)

LTL Verification of Memoryful Neural Agents
von: Hosseini, Mehran, et al.
Veröffentlicht: (2025)

A proof complexity conjecture and the Incompleteness theorem
von: Krajicek, Jan
Veröffentlicht: (2023)

A novel framework for systematic propositional formula simplification based on existential graphs
von: de Mas, Jordina Francès, et al.
Veröffentlicht: (2024)

A Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes
von: Bruse, Florian, et al.
Veröffentlicht: (2026)

An Encoding of Abstract Dialectical Frameworks into Higher-Order Logic
von: Martina, Antoine, et al.
Veröffentlicht: (2023)

Solutions of Word Equations over Partially Commutative Structures
von: Diekert, Volker, et al.
Veröffentlicht: (2016)

Descriptive complexity for neural networks via Boolean networks
von: Ahvonen, Veeti, et al.
Veröffentlicht: (2023)

From Gödel incompleteness to the consistency of circuit lower bounds
von: Atserias, Albert, et al.
Veröffentlicht: (2026)

Failure of the strong feasible disjunction property
von: Krajicek, Jan
Veröffentlicht: (2026)

The Solver's Paradox in Formal Problem Spaces
von: Rosko, Milan
Veröffentlicht: (2025)

ABox Abduction for Inconsistent Knowledge Bases under Repair Semantics
von: Haak, Anselm, et al.
Veröffentlicht: (2026)

Artifical intelligence and inherent mathematical difficulty
von: Dean, Walter, et al.
Veröffentlicht: (2024)

A Formal Analysis of Algorithms for Matroids and Greedoids
von: Abdulaziz, Mohammad, et al.
Veröffentlicht: (2025)

Varieties of Distributed Knowledge
von: Galimullin, Rustam, et al.
Veröffentlicht: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
von: Lela, Marko
Veröffentlicht: (2025)