Cover Image

A correspondence between the time and space complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Latkin, Ivan V.
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Logic in Computer Science Logic 68Q15 (Primary), 68Q17, 03D15, 03B70 (Secondary) F.1.1; F.1.3; F.2.3; F.4.1; F.4.2; F.4.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Gödel Mirror: A Formal System For Contradiction-Driven Recursion
by: Chan, Jhet
Published: (2025)

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

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

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

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

Recursive windows for grammar logics of bounded density
by: Gasquet, Olivier
Published: (2025)

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

A Logspace Constructive Proof of L=SL
by: Buss, Sam, et al.
Published: (2025)

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

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

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

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

Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)

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

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

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

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

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

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

Metalevel transformation of strategies
by: Rubio, Rubén, et al.
Published: (2024)

A Logic For Fresh Labelled Transition Systems
by: Bandukara, Mohamed H, et al.
Published: (2025)

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

$\mathbb{N}$-polyregular functions arise from well-quasi-orderings
by: Lopez, Aliaume
Published: (2024)

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

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

Complete Robust Hybrid Systems Reachability
by: Wafa, Noah Abou El, et al.
Published: (2026)

Higher-Order Pattern Unification Modulo Similarity Relations
by: Dundua, Besik, et al.
Published: (2025)

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

An Expressive Trace Logic for Recursive Programs
by: Gurov, Dilian, et al.
Published: (2024)

A Proof-Theoretic Approach to the Semantics of Classical Linear Logic
by: Barroso-Nascimento, Victor, et al.
Published: (2025)

Commutative N-polyregular functions
by: Lopez, Aliaume
Published: (2024)

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

Conformance Games for Graded Semantics
by: Forster, Jonas, et al.
Published: (2024)

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

Approximate Axiomatization for Differentially-Defined Functions
by: Platzer, André, et al.
Published: (2025)

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

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

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

On Some Complexity Results for Even Linear Languages
by: Cojocaru, Liliana
Published: (2024)