On p-creative sets and p-completely creative sets (Q1183565): Difference between revisions

This is an excellent paper dealing with an important topic in the structural complexity theory. ``\(P=NP\)?'' is the central question in the structural complexity. In 1977, \textit{M. Berman} and \textit{J. Hartmanis} [SIAM J. Comput. 6, 305-322 (1977; Zbl 0356.68059)] conjectured that all \(NP\)-complete sets are polynomial-time isomorphic. The conjecture implies \(P\neq NP\). \textit{S. Mahaney} [J. Comput. Syst. Sci. 25, 130-143 (1982; Zbl 0493.68043)] proved a result supporting this conjecture. However, in 1985, \textit{D. Joseph} and \textit{P. Young} [Theor. Comput. sci. 39, 225-237 (1985; Zbl 0597.68043)] suspected the Berman-Hartmanis conjecture by offering a new conjecture that Berman-Hartmanis conjecture is false if and only if one-way functions exist. Since the existence of the one-way function implies \(P\neq NP\), the Joseph-Young conjecture implies \(P\neq NP\), too. It is well-known that if the one-way function does not exist, then the Berman-Hartmanis conjecture is true. So, in order to prove the Joseph-Young conjecture, it suffices to study the backward direction, that is, construct \(NP\)-complete sets which are not polynomial-time isomorphic each other under condition that the one-way function exists. An important group of candidates such \(NP\)-complete sets are \(k\)-creative sets which were discovered by \textit{Joseph} and \textit{Joung} [loc. cit.]. The author made a significant progress on the study of \(k\)-creative sets.He showed that \(k\)-creativeness is in popular property for the \(m\)- complete sets in \(DEXP\) and gave a new construction for \(k\) creative sets in \(NP\).