Exponential-time and subexponential-time sets

In this paper, we prove that the symmetric difference of a ⩽P k-parity-hard set for E and a subexponential-time-computable set is still ⩽P k-parity-hard for E. This remains true for ⩽P m-hard set for E since a 1-parity reduction is a many—one reduction. In addition, we show that this property fails to hold for some other types of reductions. We introduce and study the notions of E-complete kernel and E-hard kernel.

Authors

• Shouwen Tang
• Bin Fu Institute of Computing Technology, Chinese Academy of Sciences University of Chinese Academy of Sciences
• Tian Liu

Keywords

No keywords are indexed for this paper.