Abstract

Ko, K., On the computational complexity of integral equations, Annals of Pure and Applied Logic 58 201–228. The computational complexity of Volterra integral equations of the second kind and of the first kind is investigated. It is proved that if the kernel functions satisfy the Lipschitz condition, then the solutions of Volterra equations of the second kind are polynomial-space computable. If, one the other hand, the kernel functions only satisfy the local Lipschitz condition with the Lipschitz constants growing in an exponential rate, then the solutions could be exponential-time hard. We identify a class of Volterra equations of the first kind that can be converted to Volterra equations of the second kind satisfying the local Lipschitz condition. The complexity of the solutions of these equations is also proved to be exponential-time hard