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