Universal relations

Abstract

Two operators, join and equivalence, are defined on R, a polynomial-time verifiable binary relation witnessing language A in NP. It is proved that if R has these two operators and there is an instance of A with certain specific properties, then A is NP-complete. Relations with the above properties are called universal relations. It is shown that if set A has a universal relation, then for any set B in NP, there is a reduction f from B to A such that for every x, one can recover the set of witnesses of x from that of f(x). Further, it is shown that obvious witnessing relations of some well-known complete problems as well as those of k-creative sets are universal, whereas an obvious witnessing relation for the graph isomorphism problem is not universal. Finally, it is shown that the two operators join and equivalence are closely related respectively to paddability and d -self-reducibility.