NDLI: Parallel self-reducibility

Content Provider	IEEE Xplore Digital Library
Author	Abrahamson, K. Fellows, M. Wilson, C.
Copyright Year	1992
Description	Author affiliation: Washington State Univ., Pullman, WA, USA (Abrahamson, K.)
Abstract	The authors examine the relationship between the complexity of solving a decision problem with that of solving a search problem. In particular, if they are given a solution for a decision problem in the form of an oracle, they consider the difficulty of finding evidence supporting the decision. For example, suppose they have an oracle which, when given a graph, indicates whether that graph has a Hamilton cycle (HC). The authors goal is to find a Hamilton cycle in a graph, thus proving it has one. After defining their problems using a relational model they show that if any NP-complete problem is self-reducible in parallel, then all NP-complete problems are. They also show that all P-complete problems have parallel self-reductions. Under the (unlikely) assumption that NP=co-NP, it is shown that NP-complete problems can be self-reduced. However, probabilism can be shown to help: any NP-complete problem has a randomized parallel self-reduction. Finally, natural evidence for an NP problem is discussed.<>
Starting Page	67
Ending Page	70
File Size	329455
Page Count	4
File Format	PDF
ISBN	081862812X
DOI	10.1109/ICCI.1992.227703
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1992-05-28
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Concurrent computing NP-complete problem Polynomials Computer science Search problems Information science
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in