### Abstract.

The paper establishes lower bounds on the provability of 𝒟=NP and the MRDP theorem in weak fragments of arithmetic. The theory *I*^{5}*E*_{1} is shown to be unable to prove 𝒟=NP. This non-provability result is used to show that *I*^{5}*E*_{1} cannot prove the MRDP theorem. On the other hand it is shown that *I*^{1}*E*_{1} proves 𝒟 contains all predicates of the form (∀*i*≤|*b*|)*P*(*i*,*x*)^*Q*(*i*,*x*) where ^ is =, <, or ≤, and *I*^{0}*E*_{1} proves 𝒟 contains all predicates of the form (∀*i*≤*b*)*P*(*i*,*x*)=*Q*(*i*,*x*). Here *P* and *Q* are polynomials. A conjecture is made that 𝒟 contains NLOGTIME. However, it is shown that this conjecture would not be sufficient to imply 𝒟=*N P*. Weak reductions to equality are then considered as a way of showing 𝒟=NP. It is shown that the bit-wise less than predicate, ≤_{2}, and equality are both co-NLOGTIME complete under FDLOGTIME reductions. This is used to show that if the FDLOGTIME functions are definable in 𝒟 then 𝒟=*N P*.