Submission date: 2 April 2024

Abstract:

We formalize algorithms computing Pfaffian in the theory of bounded arithmetic for sharpL which is based on Berkowitz algorithm for the determinant. We also prove relations among Pfaffian properties. Furthermore, we give an algorithm for Pfaffian pairs as well.

Mathematics Subject Classification: 03B70, 15A15, 03D15

Keywords and phrases:

Full text arXiv 2404.01728: pdf, ps.