Abstract
The symmetric differences of N P—hard sets with weakly — P-selective sets are investigated in this paper. We show that if there exist a weakly-P-selective set A and a NP-≤ p m -hard set H such that H-A ∃ P btt (Sparse) and A-H ∃ Pm (Sparse) then P=N P So no NP-≤ p m -hard set has sparse symmetric difference with any weakly-P-selective set unless P=N P. In addition we show there exists a P-selective set which has exponentially dense symmetric difference with every set in Pbtt(Sparse).
This research is supported in part by HTP863.
This research was performed while this author was visiting Beijing Computer Institute.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Reference
J.Balcarzar, J.Diaz, and J.Gabarro: Structural Complexity I,II. Springer-Verlag, 1988 and 1990.
R.Book and K.Ko: On Sets Truth-table Reducible to Sparse Sets. SIAM J.Computing 17(1988), 903–919.
B.Fu: On Lower Bounds of the Closeness between Complexity Classes. To appear in Math. Sys.Theory.
B.Fu and H.Li: On Closeness of NP-Hard sets to other Complexity Classes. Proc.7th Annual Conference in structural complexity theory, IEEE, 1992, 243–248.
K.Ko: On Self-reducibility and Weakly-P-selectivity. J.of Comp. and Sys.Sci. 26(1983), 209–211.
K.Ko: Distinguishing Bounded Reducibility by Sparse Sets. Proc.3th Conference on Structural Complexity Theory, IEEE, 1988, 181–191.
S.Mahaney: Sparse Complete Sets for NP:Solution of a Conjecture of Berman and Hartmanis. J.Comput.Sys.Sci. 25(1982), 130–143.
M.Ogiwara and O.Watanabe: On Polynomial-Time Bounded Truth-table Reducibility of NP sets to Sparse Sets. Proc. of the 22th ACM Symposium on Theory of Computing, 1990, 457–467.
U.Schöning: Complete Sets and Closeness to Complexity Classes. Math.Sys. Theory, 13(1986), 55–65.
A.L.Selman: P-selective Sets, Tally Languages and the Behavior of Polynomial-Time Reducibility on NP. Math.Sys.Theory 13(1981), 326–332.
A.L.Selman: Some Observation on NP Real Numbers and P-Selective Sets. J. Comput. Sys. Sci. 19(1981), 326–332.
A.L.Selman:Reductions on NP and P-selective Sets. Theoret.Comput.Sci. 19 (1982), 287–304.
S.Tang, B.Fu and T.Liu: Exponential Time and Subexponential Time Sets. Proc.6th Annual Conference in structural complexity theory, IEEE, 1991, 230–237.
S.Toda: On Polynomial-Time Truth Table Reducibility of Intractable Sets to P-Selective Sets. Math.Sys.Theory 24(1991), 69–82.
Y.Yesha: On Certain Polynomial-Time Truth-table Reducibilities of Complete Sets to Sparse Sets. SIAM J.Comput. 12(1983), 411–425.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fu, B., Li, Hz. (1992). On symmetric differences of NP-hard sets with weakly-P-selective sets. In: Ibaraki, T., Inagaki, Y., Iwama, K., Nishizeki, T., Yamashita, M. (eds) Algorithms and Computation. ISAAC 1992. Lecture Notes in Computer Science, vol 650. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56279-6_96
Download citation
DOI: https://doi.org/10.1007/3-540-56279-6_96
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56279-5
Online ISBN: 978-3-540-47501-9
eBook Packages: Springer Book Archive