Information Technology Reference
In-Depth Information
as a (somewhat nonstandard) witness relation for Simple Max Cut. They introduce
a more general notion of universal relations, which they call “generalized univer-
sal relations,” and show that the Simple Max Cut witness relation is generalized
universal. If one is able to show that the standard witness relations for MCSP and
FACT are not universal, then perhaps one can show that they are also not generalized
universal. This would provide some additional evidence that these problems are not
NP-complete.
Are there any additional implications that one can prove, regarding the Berman-
Hartmanis conjecture, the Creativity Hypothesis, and the question of whether all
NP-complete sets have universal witness relations?
(There has been some additional work by other authors, regarding universal rela-
tions. The reader is referred to [
CSB07
] for a discussion of this work.)
2.5 Conclusions
The notions of p-isomorphism, NP-creativity, and universality provide three ways to
identify properties that are shared by all of the “natural” NP-complete sets. Although
the work of Somenath Biswas and others has given us a body of interesting results
regarding these notions, a number of intriguing open questions remain.
Acknowledgments
Supported in part by NSF Grants CCF-0832787 and CCF-1064785.
References
[Agr96] M. Agrawal, On the isomorphism conjecture for weak reducibilities. J. Comput. Syst.
Sci.
53
(2), 267-282 (1996)
[Agr01] M. Agrawal, Towards uniform AC
0
-isomorphisms. in
Proceedings IEEE Conference
on Computational Complexity
(2001). pp. 13-20
[Agr02] M. Agrawal, Pseudo-random generators and structure of complete degrees. in
IEEE
Conference on Computational Complexity
(2002). pp. 139-147
[Agr11] M. Agrawal, The isomorphism conjecture for constant depth reductions. J. Comput.
Syst. Sci.
77
(1), 3-13 (2011)
[Agr11] M. Agrawal, in
The Isomorphism Conjecture for NP
, ed. by S.B. Cooper, A. Sorbi.
Computability in Context: Computation and Logic in the Real World (World Scientific
Press, 2011), pp. 19-48
[AA96] M. Agrawal, E. Allender, An isomorphism theorem for circuit complexity. in
Proceed-
ings IEEE Conference on Computational Complexity
(1996), pp. 2-11.
[AAIPR01] M. Agrawal, E. Allender, R. Impagliazzo, T. Pitassi, S. Rudich, Reducing the com-
plexity of reductions. Comput. Complex.
10
(2), 117-138 (2001)
[AAR98] M. Agrawal, E. Allender, S. Rudich, Reductions in circuit complexity: an isomorphism
theorem and a gap theorem. J. Comput. Syst. Sci.
57
(2), 127-143 (1998)
[AB92] M. Agrawal, S. Biswas, Universal relations. in
Proceedings IEEE Conference on Struc-
ture in Complexity Theory
(1992), pp. 207-220.
[AB96] M. Agrawal, S. Biswas, NP-creative sets: a new class of creative sets in NP. Math.
Syst. Theor.
29
(5), 487-505 (1996)
