Type of Document Dissertation Author Kozik, Marcin Andrzej URN etd-09292004-212720 Title On some complexity problems in finite algebras Degree PhD Department Mathematics Advisory Committee
Advisor Name Title Professor Ralph McKenzie Committee Chair Professor Alan Peters Committee Member Professor Alexander Ol'shanskii Committee Member Professor Constantine Tsinakis Committee Member Professor Mark Sapir Committee Member Keywords
- gamma function
- beta function
- membership problem
- universal algebra
- computational complexity
Date of Defense 2004-09-24 Availability unrestricted AbstractThis work contains constructions of finite algebras which are "complex" according to three different complexity measures.
These constructions are modifications of the construction of Ralph McKenzie's A(T).
They produce finite algebras that "model" computations of Turing machines on various inputs.
In this way, we obtain a finite algebra generating a variety with PSPACE--complete membership problem and
another algebra with exponentially growing gamma function. The final construction produces a finite algebra that is able to model a computation of a Turing machine on an exponentially long tape. This gives an example of a finite algebra with EXPSAPCE--hard membership problem and a doubly exponentially growing beta function.
Examples of finite algebra of such complexity classes were not known before.
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access ExpSpace.pdf 398.21 Kb 00:01:50 00:00:56 00:00:49 00:00:24 00:00:02