# Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis

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)?

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: