Class Description

PermUP: Self-Permuting UP

The class of languages L in UP such that the mapping from an input x to the unique witness for x is a permutation of L.

Contains P.

Defined in [HT03], where it was also shown that the closure of PermUP under polynomial-time one-to-one reductions is UP.

On the other hand, they show that if PermUP = UP then E = UE.

See also: SelfNP.

Linked From

SelfNP: Self-Witnessing NP

The class of languages L in NP such that the union, over all x in L, of the set of valid witnesses for x equals L itself.

Defined in [HT03], where it was shown that the closure of SelfNP under polynomial-time many-one reductions is NP.

They also show that if SelfNP = NP, then E = NE; and that SAT is contained in SelfNP.

See also: PermUP.

More about...