Atlas home || Conferences | Abstracts | about Atlas

Universal Algebra and Lattice Theory (Dedicated to the 70th birthday of B. Csakany)
July 22-26, 2002
University of Szeged
Szeged, Hungary

Organizers
Agnes Szendrei, Laszlo Szabo, Miklos Dorman

View Abstracts
Conference Homepage

Is it difficult to multiply 2 by 2 matrices over the 2 element field?
by
Vera Vértesi
Eötvös University, Budapest
Coauthors: Csaba Szabó

In May in Nashville M. Volkov presented a semigroup of size 2^1700 for which the word problem is co-NP-complete. In our talk we give another example by answering a question of Ross Willard from 1996: The word problem for the semigroup of the 2×2 matrices over the 2 element field is co_NP complete.

Date received: July 6, 2002

Copyright © 2002 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caiv-45.