Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis

Question

The Berman Hartmanis conjecture which formally states that there is an isomorphism for two $NP$ complete languages $L_{1}$, and $L_{2}$, the isomorphism is a bijective function $f()$ such that $f()$ maps strings from $L_{1}$ to $L_{2}$, such that $x \in L_{1}$ iff $f(x) \in L_{2}$. The isomorphism holds for all $NP$-complete languages under polynomial time assumptions(p-isomorphisms). Special conditions are: p-isomorphisms, polynomial run time $f()$, and so also the inverse of $f()$ is computable in polynomial time. The conjecture if true, would imply no $NP$-complete language is sparse. What are the analogues to the conjecture in various types of reductions, for example under $AC^{0}$ reductions the conjecture is true: Under $AC^{0}$ many-one reductions, all $NP$ complete languages do show an $AC^{0}$ isomorphism.

This leads one to the creativity conjecture, which is: Are all NP-creative sets languages the same as NP-complete sets under $\leq^{m}_{p}$ reductions. Formally, creativity for a set is defined as: A set $A$ is creative if its complement is "productive". By "productivity" of a set $A$, over a class of languages $C$, we mean there is a function(not necessarily polynomial), that witnesses $A \notin C$. So, it is natural to think of problems to be creative under different conditions, eg, a polynomial time function $f$, or even under log time, or oracular function restrictions. So, while $AC^{0}$ many-one reductions give a resolution to the Berman-Hartmanis conjecture, is there resolution to the creativity conjecture under $AC^{0}$ reductions(or any other reasonable assumptions)?

Creativity(k-creativity), like the Berman-Hartmanis conjecture(truth of which shows that there are no sparse $NP$-complete languages), shows us another fine grained level nature of $NP$ complete problems. Are there $NP$ complete problems that show creative(k-creativity, for one) properties, and some don't. Are there natural problems that that one would consider creativity, such that the $NP$-complete language is known to be creative (any variants of SAT)?

Answer 1

First of all, Mahaney's Theorem says that merely assuming $\mathsf{P} \neq \mathsf{NP}$, there are no sparse $\mathsf{NP}$-complete sets. (Historically, Mahaney was motivated to study this precisely because of Berman-Hartmanis, but the theorem is independent of BH Isomorphism.)

The $\mathsf{AC}^0$ version of the isomorphism conjecture (with various restrictions on uniformity) is a theorem. See the following paper and references therein:

Manindra Agrawal, The Isomorphism Conjecture for Constant Depth Reductions, JCSS 77 (special issue on Karp's Kyoto Prize): 3-13, 2011.

You may also be interested in other work of Agrawal, Allender, and others on related questions. Agrawal's and Allender's webpages have links to most of the relevant papers (I only say "most" in case I've missed a few that didn't involve either Agrawal or Allender, but I haven't done a thorough literature review recently).

On creativity, Joseph and Young's construction is still one of the main pieces of evidence against BH.