Loading [MathJax]/extensions/MathZoom.js
Approximable sets | IEEE Conference Publication | IEEE Xplore

Approximable sets


Abstract:

Much structural work on NP-complete sets has exploited SAT's d-self-reducibility. We exploit the additional fact that SAT is a d-cylinder to show that NP-complete sets ar...Show More

Abstract:

Much structural work on NP-complete sets has exploited SAT's d-self-reducibility. We exploit the additional fact that SAT is a d-cylinder to show that NP-complete sets are p-superterse unless P=NP. In fact, every set that is NP-hard under polynomial-time n/sup o(1/)-tt reductions is p-superterse unless P=NP. In particular no p-selective set is NP-hard under polynomial-time n/sup o(1/)-tt reductions unless P=NP. In addition, no easily countable set is NP-hard under Turing reductions unless P=NP. Self-reducibility does not seem to suffice for our main result: in a relativized world, we construct a d-self-reducible set in NP-P that is polynomial-time 2-tt reducible to a p-selective set.<>
Date of Conference: 28 June 1994 - 01 July 1994
Date Added to IEEE Xplore: 06 August 2002
Print ISBN:0-8186-5670-0
Conference Location: Amsterdam, Netherlands

Contact IEEE to Subscribe

References

References is not available for this document.