Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with unprovability:
TR15-159 | 28th September 2015
Juraj Hromkovic

Why the Concept of Computational Complexity is Hard for Verifiable Mathematics

Mathematics was developed as a strong research instrument with fully verifiable argumentations. We call any formal theory based on syntactic rules that enables to algorithmically verify for any given text whether it is a proof or not algorithmically verifiable mathematics (AV-mathematics for short). We say that a decision problem L ... more >>>

TR16-071 | 1st May 2016
Jan Krajicek, Igor Carboni Oliveira

Unprovability of circuit upper bounds in Cook's theory PV

We establish unconditionally that for every integer $k \geq 1$ there is a language $L \in P$ such that it is consistent with Cook's theory PV that $L \notin SIZE(n^k)$. Our argument is non-constructive and does not provide an explicit description of this language.

more >>>

TR19-077 | 30th May 2019
Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajicek

Consistency of circuit lower bounds with bounded theories

Proving that there are problems in $P^{NP}$ that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are known for larger complexity classes, existing results only show that the corresponding problems are hard on infinitely many input lengths. For instance, proving almost-everywhere ... more >>>

TR23-022 | 11th March 2023
Jiatu Li, Igor Carboni Oliveira

Unprovability of strong complexity lower bounds in bounded arithmetic

While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jerabek's theory $\textbf{APC}_1$ (2007) and of higher levels of Buss's hierarchy $\textbf{S}^i_2$ (1986) has been a more elusive task. Even in the more restricted setting of Cook's theory ... more >>>

TR24-083 | 18th April 2024
Lijie Chen, Jiatu Li, Igor Carboni Oliveira

On the Unprovability of Circuit Size Bounds in Intuitionistic $S^1_2$

We show that there is a constant $k$ such that Buss's intuitionistic theory $\mathbf{IS}^1_2$ does not prove that SAT requires co-nondeterministic circuits of size at least $n^k$. To our knowledge, this is the first unconditional unprovability result in bounded arithmetic in the context of worst-case fixed-polynomial size circuit lower bounds. ... more >>>

ISSN 1433-8092 | Imprint