A joint project of the Graduate School, Peabody College, and the Jean & Alexander Heard Library

Title page for ETD etd-09292004-212720


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
Abstract
This 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.

Files
  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

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LITS.