Abstract
This paper follows the methodology introduced by Agrawal and Biswas in [AB92], based on a notion of universality for the relations associated with NP-complete problems. The purpose was to study NP-complete problems by examining the effects of reductions on the solution sets of the associated witnessing relations. This provided a useful criterion for NP-completeness while suggesting structural similarities between natural NP-complete problems. We extend these ideas to the class #P. The notion we find also yields a practical criterion for #P-completeness, as illustrated by a varied set of examples, and strengthens the argument for structural homogeneity of natural complete problems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, M., Biswas, S.: Universal relations. In: Structure in Complexity Theory Conference, pp. 207–220 (1992)
Balcázar, J.L., Díaz, J., Gabarró, J.: Structural complexity 1. Springer, New York (1988)
Berman, L., Hartmanis, J.: On isomorphisms and density of NP and other complete sets. SIAM J. Comput. 6(2), 305–322 (1977)
Buhrman, H., Kadin, J., Thierauf, T.: On functions computable with nonadaptive queries to NP. In: Structure in Complexity Theory Conference, pp. 43–52 (1994)
Chakravorty, G., Kumar, R.: #P universality. Technical report, Indian Institute of Technology (2003)
Chaudhary, V., Sinha, A.K., Biswas, S.: Universality for nondeterministic logspace. In: Presented at Indo-German Workshop on Algorithms, Bangalore (2004)
Papadimitriou, C.H.: Computational complexity. Addison-Wesley Publishing Company, Reading (1994)
Poizat, B.: Les Petits Caillloux. Nur Al-Mantiq Wal-Ma’rifah, vol. 3. Aléas, Lyon (1995)
Portier, N.: Résolutions universelles pour des problèmes NP-complets. Theor. Comput. Sci. 201(1-2), 137–150 (1998)
Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865–877 (1991)
Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410–421 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fournier, H., Malod, G. (2006). Universal Relations and #P-Completeness. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds) Algorithms and Complexity. CIAC 2006. Lecture Notes in Computer Science, vol 3998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758471_35
Download citation
DOI: https://doi.org/10.1007/11758471_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34375-2
Online ISBN: 978-3-540-34378-3
eBook Packages: Computer ScienceComputer Science (R0)