# “Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes” — Worthy of arXiv.org?

Do you believe this paper is worthy of arXiv.org? I have searched via Google, and to my knowledge, no one else has this result. I'm not asking you to fully scrutinize the paper, I'm just asking if you find it worthy of archiving.

The paper appears to be my first interesting result ... ever. I'm totally new to archiving/publishing. And, relative to others, I am rather green in the logical disciplines. I produced this paper on my own; I am not studying at any institution.

If you do find it worthy of arXiv.org, and if you do have endorser privileges for Computer Science, would you be willing to endorse me? My account name is "JakeT".

I am hoping that others will find this interesting. I do.

• Without looking at the paper, I can say that the threshold for "being worthy of arxiv" is quite low. – Aryeh Oct 29 '18 at 21:41
• Just a piece of random advice -- are you associated with a university in any way? Or maybe just live near one? Showing your paper to a computer scientist would be more productive than trying to get strangers to read it on here. – Aryeh Oct 29 '18 at 22:47
• I find it interesting. If it means a lot to you, then go for it! Btw, I'm looking at it now. I've never thought about this before, so I have a question... More generally, do you think you could show that not all EXPTIME-complete problems are polynomial time isomorphic to each other? – Michael Wehar Oct 29 '18 at 23:09
• By “separates NP from superpolynomial DTIME classes”, do you mean that (for $t(n)$ superpolynomial) $\mathrm{NP\ne DTIME}(t)$, or $\mathrm{NP\nsubseteq DTIME}(t)$, or $\mathrm{DTIME}(t)\nsubseteq\mathrm{NP}$, or both of the latter, or something else? – Emil Jeřábek Oct 30 '18 at 13:26
• The output of an exponential-time reduction may have length $2^{n^c}$. The language being reduced to is computable in time exponential in its input length, which is the output length of the reduction. Thus the overall running time may be $2^{2^{n^c}}$. – Emil Jeřábek Nov 4 '18 at 11:09

• Thank you. However, to my knowledge, my argument does not relativize because it is dependent on BHC, which only makes a claim about $\mathrm{NP}$, not $\mathrm{NP}$ to some oracle. Specifically, consider where I use $\mathrm{EBH}$−$to$−$\mathrm{SAT^{−1}}$. If the argument was relativized to some oracle $\mathrm{O}$, BHC would no longer give me the function I need there: I would need a deterministic polynomial function that accepts an $\mathrm{NP^O}$−$\mathrm{Complete}$ problem (instead of SAT), and gives back my $\mathrm{EXPTIME^O}$-$\mathrm{Complete}$ problem instance. – Jake Thomas Nov 3 '18 at 23:45
• Ah. That is on my to-do list for the paper now. Also, I noticed that $\mathrm{EXPTIME}$ is not a single $\mathrm{DTIME}$ class, but an $n$-$ary$ union of them. So that's at least two things to fix. I'd like to accept your previous comment as the answer. Not having the exact time bounds worked out renders moot (or at least supersedes) the argument over whether the paper relativizes. – Jake Thomas Nov 4 '18 at 15:09