Class Description

PKC: Perfect Knowledge Complexity

Has the same relation to PZK as SKC does to SZK.

Defined in [GP91].

Linked From

SKC: Statistical Knowledge Complexity

A hierarchy of generalizations of SZK, in which Arthur is allowed to gain some information from his interaction with Merlin.

Defined in [GP91].

There are several variants (which we only describe roughly), including:

See also: PKC.

More about...