Rankings
Publications
Search Publications
Cited-by Search
Sources
Publishers
Scholars
Scholars
Top Cited Scholars
Organizations
About
Scilit
About Us
Advisory Board
Data Sources
Career
Support / Contact
User Guide
Publisher User
Search Function
Rankings Function
API Resource
Scilit Knowledge
Metrics
Scilit Recognitions
Publications Classification
Media
News
Blog
Login
Register
Home
Publications
#P-COMPLETENESS VIA MANY-ONE REDUCTIONS
Home
Publications
#P-COMPLETENESS VIA MANY-ONE REDUCTIONS
#P-COMPLETENESS VIA MANY-ONE REDUCTIONS
Author:
VZ
Viktória Zankó
Viktória Zankó
Article Alert
Citation Alert
Add to Library
Cite
Download
Share
Download
Publisher website
Google Scholar
1 March 1991
journal article
research article
Published by
World Scientific Pub Co Pte Ltd
in
International Journal of Foundations of Computer Science
Vol. 02
(01)
,
77-82
DOI:
10.1142/s0129054191000066
Abstract
Valiant defined #P-completeness using Turing reductions. We propose a more restrictive definition, a variant of many-one reductions, and prove that the (0, 1)-permanent remains #P-complete under this definition.
Keywords
COMPLEXITY
REDUCIBILITY
COUNTING
PERMANENT
Related articles
Cited
Cited by 70 articles
Scroll to top