Universal relations and #P-completeness
| Autor: | Guillaume Malod, Hervé Fournier |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
General Computer Science
Computational complexity theory Counting problems Solution set Hamiltonian path Universal relation Similitude Universality (dynamical systems) Theoretical Computer Science Computational complexity symbols.namesake Counting problem symbols Calculus NP-complete Mathematical economics Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 407(1-3):97-109 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2008.05.003 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect