Cover Image

From Gödel incompleteness to the consistency of circuit lower bounds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Atserias, Albert, Müller, Moritz
Format:	Preprint
Published:	2026
Subjects:	Logic Computational Complexity 03F20, 03F30, 68Q15
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2024)

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

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

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

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

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

Semi-Algebraic Proof Systems for QBF
by: Beyersdorff, Olaf, et al.
Published: (2025)

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

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

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

Finite Combinatorics and Fragments of Arithmetic
by: Wang, Wei
Published: (2025)

A non-speedup result for the chain-antichain principle over a weak base theory
by: Kowalik, Katarzyna W.
Published: (2025)

The Optimizer Quotient and the Certification Trilemma
by: Simas, Tristan
Published: (2026)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2024)

A Cut-Free Sequent Calculus for the Analysis of Finite-Trace Properties in Concurrent Systems
by: Fusco, Ludovico, et al.
Published: (2025)

From Numbers to Container Strings
by: Visser, Albert
Published: (2024)

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

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

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

A Minimal Substitution Basis for the Kalmár Elementary Functions
by: Prunescu, Mihai, et al.
Published: (2025)

Gödel's incompleteness theorem and the Anti-Mechanist Argument: revisited
by: Cheng, Yong
Published: (2019)

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

Tightness and solidity in fragments of Peano Arithmetic
by: Gruza, Piotr, et al.
Published: (2025)

Feferman's completeness theorem
by: Pakhomov, Fedor, et al.
Published: (2024)

On the hierarchy of natural theories
by: Walsh, James
Published: (2021)

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

On a Question of Hamkins'
by: Visser, Albert
Published: (2025)

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

Pour-El's Landscape
by: Kurahashi, Taishi, et al.
Published: (2023)

Consistency formula is strictly stronger in PA than PA-consistency
by: Artemov, Sergei
Published: (2025)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

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

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

Proving Unsatisfiability with Hitting Formulas
by: Filmus, Yuval, et al.
Published: (2023)

Exploring P versus NP
by: Tang, Jian-Gang
Published: (2022)

Extensional Independence
by: Kurahashi, Taishi, et al.
Published: (2025)

Completions of Restricted Complexity I, Weak Arithmetical Theories
by: Enayat, Ali, et al.
Published: (2025)