Computing the Boolean product of two n\times n Boolean matrices using O(n^2) mechanical operation

Autor:	Lingas, Andrzej, Persson, Mia
Rok vydání:	2020
Předmět:	Computer Science - Data Structures and Algorithms F.4.1 F.2.2
Druh dokumentu:	Working Paper
Popis:	We study the problem of determining the Boolean product of two n\times n Boolean matrices in an unconventional computational model allowing for mechanical operations. We show that O(n^2) operations are sufficient to compute the product in this model. Comment: 11 pages, 7 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2004.13086 Zobrazit plný text záznamu View this record from Arxiv