# “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 supports Monica 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 supports Monica Nov 4 '18 at 11:09

## 1 Answer

I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = EXP.

The main issue is that you can't do self-reference for time-bounded machines since you can't simulate and stay within the time bound.

• 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
• Secondly, I'm not understanding why self-reference for time-bounded machines is forbidden. I'm not simulating anything, and even if I was, how does this break the time bound? Is it because I'm not accounting for the overhead of simulation? And, of course, I'm passing the program in by reference, since passing it in by value would result in an infinitely large parameter, as it would in Turing's self-reference proof of the Halting Problem's uncomputability. – Jake Thomas Nov 4 '18 at 0:09
• All I can suggest is to work through your argument with specific time bounds instead of just saying exponential. Remember that a reduction to SAT, or an isomorphism, can blow up the input by a polynomial length. – Lance Fortnow Nov 4 '18 at 13:29
• 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