Class Description

(M_k)P: Acceptance Mechanism by Monoid M_k

A monoid is a set with an associative operation and an identity element (so it's like a group, except that it need not have inverses).

Then (M_k)P is the class of decision problems solvable by an NP machine with the following acceptance mechanism. The i^th computation path (under some lexicographic ordering) outputs an element m_i of M_k. Then the machine accepts if and only if m₁m₂...m_s is the identity (where s is the number of paths).

Defined by Hertrampf [Her97], who also showed the following (in the special case M is a group):

• If G is any nonsolvable group (for example S₅, the symmetric group on 5 elements), then (G)P = PSPACE.
• (Z_k)P = coMod_kP, where Z_k is the cyclic group on k elements.
• If |G|=k, then (G)P contains coMod_kP.

Linked From

No class.