Cover Image

A Logspace Constructive Proof of L=SL

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Buss, Sam, Dhayal, Anant, Kabanets, Valentine, Kolokolova, Antonina, Mouli, Sasank
Format:	Preprint
Published:	2025
Subjects:	Logic in Computer Science Logic 03D15, 03F30, 03F35, 68Q15, 68Q10 F.4.1; F.1.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Arithmetics within the Linear Time Hierarchy
by: Pollett, Chris
Published: (2025)

A proof complexity conjecture and the Incompleteness theorem
by: Krajicek, Jan
Published: (2023)

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

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

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

The Orientation Boundary for Step-Duplicating Recursors: Mechanized Impossibility, Escape, and Certification
by: Rahnama, Moses
Published: (2025)

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

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

The equational theory of the Weihrauch lattice with (iterated) composition
by: Pradic, Cécilia
Published: (2024)

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

Why the classes P and NP are not well-defined finitarily
by: Anand, Bhupinder Singh
Published: (2024)

On the computational properties of ambivalent sets and functions
by: Normann, Dag, et al.
Published: (2026)

Computability of Initial Value Problems
by: Brattka, Vasco, et al.
Published: (2024)

A declarative approach to specifying distributed algorithms using three-valued modal logic
by: Gabbay, Murdoch J., et al.
Published: (2025)

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

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Do not throw out the baby: Clarithmetics as alternatives to weak arithmetics
by: Japaridze, Giorgi
Published: (2026)

A propositional cirquent calculus for computability logic
by: Japaridze, Giorgi
Published: (2024)

The Aurellion Function: A Recursive Fast-Growing Hierarchy Beyond Knuth Notation
by: Vodrazka, Daniel
Published: (2025)

Remarks on Primitive Regulation
by: Rosko, Milan
Published: (2026)

Proof complexity of universal algebra in a CSP dichotomy proof
by: Gaysin, Azza
Published: (2024)

Computing Distinguishing Formulae for Threshold-Based Behavioural Distances
by: Forster, Jonas, et al.
Published: (2026)

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

Algebraic Proof Theory for Infinitary Action Logic
by: Fussner, Wesley, et al.
Published: (2025)

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

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

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

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)

Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2025)

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

E-variables and tests of randomness for distribution classes
by: Potapov, Georgii, et al.
Published: (2026)

Behavioural Conformances based on Lax Couplings
by: Wild, Paul, et al.
Published: (2025)

Weak and Strong Versions of Effective Transfinite Recursion
by: Uftring, Patrick
Published: (2022)

On the Realizability of Prime Conjectures in Heyting Arithmetic
by: Rosko, Milan
Published: (2025)

Quantitative Graded Semantics and Spectra of Behavioural Metrics
by: Forster, Jonas, et al.
Published: (2023)

Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
by: Lopez, Aliaume
Published: (2024)

Tao's Equational Proof Challenge Accepted (Technical Report)
by: Kondylidou, Lydia, et al.
Published: (2026)

Relative Constructibility via Generalised Sequential Algorithms
by: Lau, Desmond
Published: (2024)