Cover Image

A proof complexity conjecture and the Incompleteness theorem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Krajicek, Jan
Format:	Preprint
Published:	2023
Subjects:	Logic in Computer Science Logic 03F20, 03F40, 68Q15 F.1.3; F.4.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
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)

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

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

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

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

Glivenko's theorems from an ecumenical perspective
by: Pereira, Luiz Carlos, et al.
Published: (2026)

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

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

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

Cut elimination for propositional cyclic proof systems with fixed-point operators
by: Hori, Hiromasa, et al.
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)

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

Internal Effectful Forcing in System T
by: Escardo, Martin H., et al.
Published: (2025)

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

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

Coinductive proof search for polarized logic with applications to full intuitionistic propositional logic
by: Santo, José Espírito, et al.
Published: (2020)

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

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

Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof
by: Borzechowski, Manfred, et al.
Published: (2025)

Symmetries in Sorting
by: Choudhury, Vikraman, et al.
Published: (2025)

Thoughts on sub-Turing interactive computability
by: Japaridze, Giorgi
Published: (2024)

Proof Compression via Subatomic Logic and Guarded Substitutions
by: Barrett, Victoria, et al.
Published: (2025)

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 Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes
by: Bruse, Florian, et al.
Published: (2026)

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

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

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
by: Grochow, Joshua A., et al.
Published: (2022)

Finitary Simulation of Infinitary $β$-Reduction via Taylor Expansion, and Applications
by: Cerda, Rémy, et al.
Published: (2022)

Simply-typed constant-domain modal lambda calculus I: distanced beta reduction and combinatory logic
by: Walsh, Sean
Published: (2024)

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

On the relative asymptotic expressivity of inference frameworks
by: Koponen, Vera, et al.
Published: (2022)

A Guide to Krivine Realizability for Set Theory
by: Matthews, Richard
Published: (2023)

Extracting total Amb programs from proofs
by: Berger, Ulrich, et al.
Published: (2023)