Universal relations

Agrawal, Manindra ; Biswas, Somenath (1992) Universal relations Proceedings of the Seventh Annual Structure in Complexity Theory Conference . pp. 207-220.

PDF - Author Version

Official URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?...

Related URL: http://dx.doi.org/10.1109/SCT.1992.215395


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.

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:92033
Deposited On:26 May 2012 13:52
Last Modified:19 May 2016 05:37

Repository Staff Only: item control page