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

PDF
 Author Version
315kB 
Official URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?...
Related URL: http://dx.doi.org/10.1109/SCT.1992.215395
Abstract
Two operators, join and equivalence, are defined on R, a polynomialtime 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 NPcomplete. 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 wellknown complete problems as well as those of kcreative 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 selfreducibility.
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