Cover Image

Computational Complexity of Physical Counting

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Simas, Tristan
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity Logic in Computer Science Mathematical Physics Category Theory 82B35, 20C35, 68Q15, 68Q17, 94A15, 94A17, 03B35, 82B31, 20B30 F.1.3; F.2.2; G.2.1; H.1.1; I.2.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Understanding and Improving Automated Proof Synthesis for Interactive Theorem Provers
by: Zhang, Manqing, et al.
Published: (2026)

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

Truth-Aware Decoding: A Program-Logic Approach to Factual Language Generation
by: Alpay, Faruk, et al.
Published: (2025)

Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

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

Formalizing Pick's Theorem in Isabelle/HOL
by: Binder, Sage, et al.
Published: (2024)

Domains, Information Frames, and Their Logic
by: Spreen, Dieter
Published: (2025)

A Modular Lean 4 Framework for Confluence and Strong Normalization of Lambda Calculi with Products and Sums
by: Ramos, Arthur, et al.
Published: (2025)

How Does Machine Learning Manage Complexity?
by: Fortnow, Lance
Published: (2026)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

Formally Verifying a Transformation from MLTL Formulas to Regular Expressions
by: Wang, Zili, et al.
Published: (2025)

Formalizing MLTL Formula Progression in Isabelle/HOL
by: Kosaian, Katherine, et al.
Published: (2024)

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
by: Bannach, Max, et al.
Published: (2025)

Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
by: Goldberg, Guy, et al.
Published: (2025)

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)

Locality, Consistency, and the Tractability Frontier
by: Simas, Tristan
Published: (2026)

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

Universal Algebra in UniMath
by: Amato, Gianluca, et al.
Published: (2021)

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

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

Virasoro algebra and Sugawara constructions formally in Lean
by: Kytölä, Kalle
Published: (2025)

Nominal techniques as an Agda library
by: Gabbay, Murdoch J., et al.
Published: (2026)

Conserved active information
by: Chen, Yanchen, et al.
Published: (2025)

Separation of PSPACE and EXP
by: Czerwinski, Reiner
Published: (2021)

A Homological Separation of $\mathbf{P}$ from $\mathbf{NP}$ via Computational Topology and Category Theory
by: Tang, Jian-Gang
Published: (2025)

Continuous and algebraic domains in univalent foundations
by: de Jong, Tom, et al.
Published: (2024)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Approximate Distributed Coded Computing: Polynomial Codes and Randomized Sketching
by: Charalambides, Neophytos, et al.
Published: (2026)

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

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

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

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
by: Rossman, Benjamin
Published: (2024)

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

Description Logics with Two Types of Definite Descriptions: Complexity, Expressiveness, and Automated Deduction
by: Sochański, Michał, et al.
Published: (2025)

Determination of the fifth Busy Beaver value
by: The bbchallenge Collaboration, et al.
Published: (2025)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
by: Lela, Marko
Published: (2025)

The Polynomial Hierarchy does not collapse
by: Czerwinski, Reiner
Published: (2024)

Universal Gluing and Contextual Choice: Categorical Logic and the Foundations of Analytic Approximation
by: Santacana, Andreu Ballus
Published: (2025)

An Alternative Approach to Formal Mathematics that Focuses on Communication and Accessibility
by: Farmer, William M.
Published: (2026)