University of Cambridge > > Isaac Newton Institute Seminar Series > Root finding in TC^0 and open induction

Root finding in TC^0 and open induction

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

It is known that elementary arithmetic operations are computable in uniform TC0, and some (multiplication, division) are even complete for this complexity class. The corresponding theory of bounded arithmetic, VTC 0, duly defines addition, multiplication, and ordering, and proves that integers form a discretely ordered ring under these operations. It is a natural question what other first-order properties of elementary arithmetic operations are provable in VTC 0. In particular, we are interested whether VTC 0 (or a theory of similar strength) can prove open induction in the basic language of arithmetic (Shepherdson’s theory IOpen). This turns out equivalent to the problem whether there are TC0 root-finding algorithms for constant-degree polynomials whose soundness is provable in VTC 0. In this talk, we will establish that such root-finding algorithms exist in the real (or rather, complex) world, and we will discuss the prospects of their formalization in bounded arithmetic.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity