Zobrazeno 1 - 10
of 2 234
pro vyhledávání: '"bounded arithmetic"'
Autor:
Kuroda, Satoru
We formalize algorithms computing Pfaffian in the theory of bounded arithmetic for sharpL which is based on Berkowitz algorithm for the determinant. We also prove relations among Pfaffian properties. Furthermore, we give an algorithm for Pfaffian pai
Externí odkaz:
http://arxiv.org/abs/2404.01728
Autor:
Li, Jiatu, Oliveira, Igor Carboni
While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Je\v{r}\'abek's theory $APC_1$ (2007) and of higher levels of Buss's hierarchy $S^i_2$ (198
Externí odkaz:
http://arxiv.org/abs/2305.15235
Autor:
Volfson, Victor
The paper considers estimates for the asymptotics of summation functions of bounded multiplicative arithmetic functions. Several assertions on this subject are proved and examples are considered.
Comment: 13 pages
Comment: 13 pages
Externí odkaz:
http://arxiv.org/abs/2304.01206
Autor:
YAMAGATA, YORIYUKI
Publikováno v:
The Journal of Symbolic Logic, 2018 Sep 01. 83(3), 1063-1090.
Externí odkaz:
https://www.jstor.org/stable/26600362
Autor:
Narusevych, Mykyta
We give elementary proof that theory $T^1_2(R)$ augmented by the weak pigeonhole principle for all $\Delta^b_1(R)$-definable relations does not prove the bijective pigeonhole principle for $R$. This can be derived from known more general results but
Externí odkaz:
http://arxiv.org/abs/2208.14713
Autor:
Beckmann, Arnold, Yamagata, Yoriyuki
We consider pure equational theories that allow substitution but disallow induction, which we denote as PETS, based on recursive definition of their function symbols. We show that the Bounded Arithmetic theory $S^1_2$ proves the consistency of PETS.
Externí odkaz:
http://arxiv.org/abs/2203.04832
Autor:
Krajíček, Jan
Publikováno v:
The Journal of Symbolic Logic, 1997 Jun 01. 62(2), 457-486.
Externí odkaz:
https://www.jstor.org/stable/2275541
Autor:
Zambella, Domenico
Publikováno v:
The Journal of Symbolic Logic, 1996 Sep 01. 61(3), 942-966.
Externí odkaz:
https://www.jstor.org/stable/2275794
Autor:
Beckmann, Arnold
Publikováno v:
The Journal of Symbolic Logic, 2002 Mar 01. 67(1), 279-296.
Externí odkaz:
https://www.jstor.org/stable/2695010