Paper Info
Title
Universal relations and #P-completeness
Abstract
This paper follows the methodology introduced by Agrawal and Biswas in [Manindra Agrawal, Somenath Biswas, Universal relations, in: Structure in Complexity Theory Conference, 1992, pp. 207-220], 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.
Year
DOI
Venue
2006
10.1016/j.tcs.2008.05.003
Theoretical Computer Science
Keywords
Field
DocType
NP-complete problem,natural NP-complete problem,Manindra Agrawal,Somenath Biswas,natural complete problem,practical criterion,structural homogeneity,structural similarity,useful criterion,Complexity Theory Conference,universal relation
Similitude,Combinatorics,NP-complete,Universal relation,Hamiltonian path,Solution set,Universality (philosophy),Completeness (statistics),Mathematics,Computational complexity theory
Conference
Volume
Issue
ISSN
407
1-3
Theoretical Computer Science
ISBN
Citations 
PageRank 
3-540-34375-X
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Hervé Fournier118518.10
Guillaume Malod2544.53