Root finding in TC^0 and open induction

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

• Jerbek, E (Academy of Sciences of the Czech Republic)
• Friday 30 March 2012, 10:00-10:30
• Seminar Room 1, Newton Institute.

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 TC^{0, 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 TC^{0 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.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.