Computing the Boolean Product of Two n × n Boolean Matrices Using O(n2) Mechanical Operations
Andrzej Lingas and Mia Persson
We study the problem of determining the Boolean product of two n × n Boolean matrices in an unconventional computational model allowing for mechanical operations. We show that O(n2) operations are sufficient to compute the product in this model.
Keywords: Boolean matrix multiplication, Boolean matrix-vector multiplication, mechanical computing, time complexity