Eylem Seç
Hardness Results for the Subpower Membership Problem
Başlık:
Hardness Results for the Subpower Membership Problem
Yazar:
Shriner, Jeffrey Alan, author.
ISBN:
9780355965407
Yazar Ek Girişi:
Fiziksel Tanımlama:
1 electronic resource (60 pages)
Genel Not:
Source: Dissertation Abstracts International, Volume: 79-10(E), Section: B.
Advisors: Agnes Szendrei Committee members: William DeMeo; Joshua Grochow; Keith Kearnes; Peter Mayr; Agnes Szendrei.
Özet:
We first provide an example of a finite algebra with a Taylor term whose subpower membership problem is NP-hard. We then prove that for any consistent strong linear Maltsev condition M which does not imply the existence of a cube term, there exists a finite algebra satisfying M whose subpower membership problem is EXPTIME-complete. We characterize consistent strong linear Maltsev conditions which do not imply the existence of a cube term, and show as a corollary that there are finite algebras which generate congruence distributive and congruence k-permutable (k greater than or equal to 3) varieties whose subpower membership problem is EXPTIME-complete. Finally, we show that the spectrum of complexities of the problems SMP(A) for finite algebras A in varieties which are congruence distributive and congruence k-permutable (k greater than or equal to 3) is fuller than P and EXPTIME-complete by giving examples of finite algebras in such a variety whose subpower membership problems are NP-complete and PSPACE-complete, respectively.
Notlar:
School code: 0051
Tüzel Kişi Ek Girişi:
Mevcut:*
Yer Numarası | Demirbaş Numarası | Shelf Location | Lokasyon / Statüsü / İade Tarihi |
---|---|---|---|
XX(679514.1) | 679514-1001 | Proquest E-Tez Koleksiyonu | Arıyor... |
On Order
Liste seç
Bunu varsayılan liste yap.
Öğeler başarıyla eklendi
Öğeler eklenirken hata oldu. Lütfen tekrar deneyiniz.
:
Select An Item
Data usage warning: You will receive one text message for each title you selected.
Standard text messaging rates apply.