A Note on Induction Schemas in Bounded Arithmetic

Details A Note on Induction Schemas in Bounded Arithmetic A Note on Induction Schemas in Bounded Arithmetic

2002-10-14

arxiv.org/abs/cs/0210011v1

Computer Science

Logic in Computer Science

Scientific paper

As is well known, Buss' theory of bounded arithmetic $S^{1}_{2}$ proves
$\Sigma_{0}^{b}(\Sigma_{1}^{b})-LIND$; however, we show that Allen's
$D_{2}^{1}$ does not prove $\Sigma_{0}^{b}(\Sigma_{1}^{b})-LLIND$ unless $P =
NC$. We also give some interesting alternative axiomatisations of $S^{1}_{2}$.

Affiliated with

Also associated with

No associations

Rating

A Note on Induction Schemas in Bounded Arithmetic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Note on Induction Schemas in Bounded Arithmetic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on Induction Schemas in Bounded Arithmetic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-412053