Universal relations
Universal relations
复制标题
普遍关系
DOI：
10.1109/sct.1992.215395
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Somenath Biswas
中科院分区：
文献类型：
--
作者：
Manindra Agrawal;Somenath Biswas
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.<<ETX>>
