<p>I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and <a href="https://bibbase.org/network/publication/beigel-buhrman-fortnow-npmightnotbeaseasyasdetectinguniquesolutions-1998" rel="noreferrer">there is an oracle</a> relative to which the Berman-Hartmanis conjecture is true and NP = EXP. </p>

<p>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.</p>

CC BY-SA 4.0
2018-11-03T23:45:09.427Z
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
CC BY-SA 4.0
2018-11-04T00:09:57.533Z
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
CC BY-SA 4.0
2018-11-04T13:29:16.467Z
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
CC BY-SA 4.0
2018-11-04T15:09:51.020Z
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
CC BY-SA 4.0
2018-11-02T21:36:24.930Z
2018-11-02T21:36:24.930Z
Lance Fortnow
<p>Do you believe <a href="https://www.dropbox.com/s/lbg0n9r9r1jd22z/BHC%20Separates%20NP%20From%20All%20Super-Poly%20DTIME%20Classes.pdf?dl=0" rel="noreferrer">this paper</a> 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.</p>

<p>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.</p>

<p>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".</p>

<p>I am hoping that others will find this interesting. I do.</p>

CC BY-SA 4.0
2018-10-29T21:41:30.907Z
Without looking at the paper, I can say that the threshold for "being worthy of arxiv" is quite low.
Aryeh
CC BY-SA 4.0
2018-10-29T22:47:32.540Z
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
CC BY-SA 4.0
2018-10-29T23:09:16.023Z
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
CC BY-SA 4.0
2018-10-29T23:12:26.520Z
If you could prove this more general statement, then I think that your proposed theorem would nicely follow as a corollary.
Michael Wehar
CC BY-SA 4.0
2018-10-29T23:27:49.260Z
I guess all I'm saying is that there could be some interesting further questions to explore.  If you ever want to talk about this, I would be happy to.  :)
Michael Wehar
CC BY-SA 4.0
2018-10-30T13:26:32.700Z
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
CC BY-SA 4.0
2018-10-31T06:16:29.167Z
Wow! Thank you, everyone, for such prompt and supportive feedback! I wish I could have gotten back sooner, but things have been busy.
Jake Thomas
CC BY-SA 4.0
2018-10-31T06:16:50.220Z
@Aryeh I have not been associated with any university since my graduation, nor do I live near one. I looked for my former profs on arXiv.org, but they do not have papers there. So they would not be able to endorse me.

But anyhow, it’s nice knowing I have a chance of getting on arXiv  ; p.
Jake Thomas
CC BY-SA 4.0
2018-10-31T06:20:07.413Z
@Michael Wehar  What an interesting thought! That was not part of my original thinking. But it has my interest! I’ll be thinking about it, for sure. (My original train of thought needs to be given as a link. Will do soon.) I would like to talk about this some more.
Jake Thomas
CC BY-SA 4.0
2018-10-31T06:22:30.433Z
@MichaelWehar, What you mention is only "more general" if it applies to all super-polynomial DTIME classes. You only mention EXPTIME. Take for example, the complexity class of all problems solvable in quasi-polynomial time. Emil is hinting at more to explore as well. I think other ideas should be additional papers. All very exciting!
Jake Thomas
CC BY-SA 4.0
2018-10-31T06:25:47.923Z
@Emil Jeřábek Thank you for your question. You made me realize something I had not given thought to. Directly, I only speak of complexity class inequality, leaving it up to the reader to make the trivial observation that under BHC, because EXPTIME does not equal NP, NP must be a strict sub-class of EXPTIME, since SAT is solvable in exponential time. Further, we already know that NP is a strict sub-class of all DTIME classes beyond EXPTIME, for the same reason.
Jake Thomas
CC BY-SA 4.0
2018-10-31T06:26:24.903Z
@Emil Jeřábek  But, consider the complexity class of all problems solvable in quasi-polynomial time. We’ll call it QP. By the paper and BHC, we’d only know that QP does not equal NP and that they must at least intersect at P. Whether one includes all of the other would be another question. The paper shows that the quasi-polynomial-complete problem of Quasi-Polynomially Bounded Halting cannot be polynomially reduced to SAT under BHC, and therefore, QP and NP do not equal. It would be interesting to try and extend this result to find strict containment of QP in NP or vise versa.
Jake Thomas
CC BY-SA 4.0
2018-10-31T06:36:49.303Z
In case anyone is interested, [here's](https://www.dropbox.com/s/4aqnvrik08ih1k8/Train%20of%20Thought.pdf?dl=0) how my thought process around this evolved, along with some proofs of some very simple concepts.
Jake Thomas
CC BY-SA 4.0
2018-10-31T09:45:21.090Z
As far as I can see, $\mathrm{QP\ne NP}$ holds unconditionally: QP is closed under quasipolynomial-time reductions, but NP is not, because by a padding argument, its closure under quasipolynomial-time reductions is NQP, which is strictly larger than NP by the nondeterministic time-hierarchy theorem.
Emil Jeřábek
CC BY-SA 4.0
2018-10-31T10:02:57.340Z
(By NQP, I meant nondeterministic quasipolynomial time. I see that the abbreviation is already used for nondeterministic quantum polynomial time, which is something else entirely.)
Emil Jeřábek
CC BY-SA 4.0
2018-10-31T22:05:03.763Z
I think I would edit the structure a bit first, though I think the content is definitely worthy of storing in a public, open place.
Samuel Schlesinger
CC BY-SA 4.0
2018-11-01T23:57:35.640Z
@Emil I am new to the padding argument. But I'm tempted to think that if your argument is sound, then $\mathrm{EXTIME \neq NP}$ is unconditional as well, unless the padding argument does not work with exponential reductions. *i.e.*, isn't $\mathrm{EXPTIME}$ closed under exponential reductions, and by logic similar to your argument, isn't the closure of $\mathrm{NP}$ under exponential reductions $\mathrm{NEXP}$, which, again, by the Non-Deterministic Time-Hierarchy Theorem is strictly larger than $\mathrm{NP}$?
Jake Thomas
CC BY-SA 4.0
2018-11-02T00:27:06.403Z
@Samuel Thank you. But I think it's actually going to get a major overhaul. I have revisited Michael's comment, and, yes, I think it could be a much more interesting paper with only a little more work.
Jake Thomas
CC BY-SA 4.0
2018-11-02T00:27:41.570Z
Sorry for being dense, Michael. I should have given your suggestion a little more thought before saying "other ideas should be additional papers." I was just worried the paper would never get done if I kept changing the main idea. But I think your thought will require only a little more work; I'll reference you.
Jake Thomas
CC BY-SA 4.0
2018-11-02T09:11:35.817Z
No, EXPTIME is not closed under exponential-time reductions. It is only closed under polynomial-time reductions.
Emil Jeřábek
CC BY-SA 4.0
2018-11-02T12:25:20.957Z
However, you can use the same argument to show for example that $\mathrm{NP\ne E}$, as (unlike EXP) E is not even closed under polynomial-time reductions.
Emil Jeřábek
CC BY-SA 4.0
2018-11-04T00:30:41.147Z
@Emil Thank you for telling me about $\mathrm{E}$, especially that part about $\mathrm{NP \neq E}$. That makes sense to me, since the latter is limited to strictly linear exponents and therefore is limited to linear reductions, not polynomial ones in general.
Jake Thomas
CC BY-SA 4.0
2018-11-04T01:09:15.823Z
@Emil However, I could really use a link to something explaining why $\mathrm{EXPTIME}$ is not closed under exponential reductions. Intuitively, if I multiply the steps an algorithm takes by an exponential, and it already took an exponential number of steps, I get something like this: $2^{n} \times 2^{n} = 2^{2 \times n}$. So why can I not take an algorithm for a problem in $\mathrm{EXPTIME}$, apply an exponential reduction to it, and have an algorithm that solves another problem in $\mathrm{EXPTIME}$, even if I use that reduction in each step?
Jake Thomas
CC BY-SA 4.0
2018-11-04T11:09:13.633Z
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
<complexity-classes><np><research-practice><conditional-results><halting-problem>
"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?
Jake Thomas
# "Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?

(Asked by: username_0 on 2018-10-29)

Do you believe [this paper](https://www.dropbox.com/s/lbg0n9r9r1jd22z/BHC%20Separates%20NP%20From%20All%20Super-Poly%20DTIME%20Classes.pdf?dl=0) 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.

**Tags:** complexity-classes, np, research-practice, conditional-results, halting-problem
> **Comments:**
> **username_1**: Without looking at the paper, I can say that the threshold for "being worthy of arxiv" is quite low.  
> **username_1**: 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.  
> **username_2**: 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?  
> **username_2**: If you could prove this more general statement, then I think that your proposed theorem would nicely follow as a corollary.  
> **username_2**: I guess all I'm saying is that there could be some interesting further questions to explore.  If you ever want to talk about this, I would be happy to.  :)  
> **username_3**: 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?  
> **username_0**: Wow! Thank you, everyone, for such prompt and supportive feedback! I wish I could have gotten back sooner, but things have been busy.  
> **username_0**: @Aryeh I have not been associated with any university since my graduation, nor do I live near one. I looked for my former profs on arXiv.org, but they do not have papers there. So they would not be able to endorse me.  But anyhow, it’s nice knowing I have a chance of getting on arXiv  ; p.  
> **username_0**: @Michael Wehar  What an interesting thought! That was not part of my original thinking. But it has my interest! I’ll be thinking about it, for sure. (My original train of thought needs to be given as a link. Will do soon.) I would like to talk about this some more.  
> **username_0**: @MichaelWehar, What you mention is only "more general" if it applies to all super-polynomial DTIME classes. You only mention EXPTIME. Take for example, the complexity class of all problems solvable in quasi-polynomial time. Emil is hinting at more to explore as well. I think other ideas should be additional papers. All very exciting!  
> **username_0**: @Emil Jeřábek Thank you for your question. You made me realize something I had not given thought to. Directly, I only speak of complexity class inequality, leaving it up to the reader to make the trivial observation that under BHC, because EXPTIME does not equal NP, NP must be a strict sub-class of EXPTIME, since SAT is solvable in exponential time. Further, we already know that NP is a strict sub-class of all DTIME classes beyond EXPTIME, for the same reason.  
> **username_0**: @Emil Jeřábek  But, consider the complexity class of all problems solvable in quasi-polynomial time. We’ll call it QP. By the paper and BHC, we’d only know that QP does not equal NP and that they must at least intersect at P. Whether one includes all of the other would be another question. The paper shows that the quasi-polynomial-complete problem of Quasi-Polynomially Bounded Halting cannot be polynomially reduced to SAT under BHC, and therefore, QP and NP do not equal. It would be interesting to try and extend this result to find strict containment of QP in NP or vise versa.  
> **username_0**: In case anyone is interested, [here's](https://www.dropbox.com/s/4aqnvrik08ih1k8/Train%20of%20Thought.pdf?dl=0) how my thought process around this evolved, along with some proofs of some very simple concepts.  
> **username_3**: As far as I can see, $\mathrm{QP\ne NP}$ holds unconditionally: QP is closed under quasipolynomial-time reductions, but NP is not, because by a padding argument, its closure under quasipolynomial-time reductions is NQP, which is strictly larger than NP by the nondeterministic time-hierarchy theorem.  
> **username_3**: (By NQP, I meant nondeterministic quasipolynomial time. I see that the abbreviation is already used for nondeterministic quantum polynomial time, which is something else entirely.)  
> **username_4**: I think I would edit the structure a bit first, though I think the content is definitely worthy of storing in a public, open place.  
> **username_0**: @Emil I am new to the padding argument. But I'm tempted to think that if your argument is sound, then $\mathrm{EXTIME \neq NP}$ is unconditional as well, unless the padding argument does not work with exponential reductions. *i.e.*, isn't $\mathrm{EXPTIME}$ closed under exponential reductions, and by logic similar to your argument, isn't the closure of $\mathrm{NP}$ under exponential reductions $\mathrm{NEXP}$, which, again, by the Non-Deterministic Time-Hierarchy Theorem is strictly larger than $\mathrm{NP}$?  
> **username_0**: @Samuel Thank you. But I think it's actually going to get a major overhaul. I have revisited Michael's comment, and, yes, I think it could be a much more interesting paper with only a little more work.  
> **username_0**: Sorry for being dense, Michael. I should have given your suggestion a little more thought before saying "other ideas should be additional papers." I was just worried the paper would never get done if I kept changing the main idea. But I think your thought will require only a little more work; I'll reference you.  
> **username_3**: No, EXPTIME is not closed under exponential-time reductions. It is only closed under polynomial-time reductions.  
> **username_3**: However, you can use the same argument to show for example that $\mathrm{NP\ne E}$, as (unlike EXP) E is not even closed under polynomial-time reductions.  
> **username_0**: @Emil Thank you for telling me about $\mathrm{E}$, especially that part about $\mathrm{NP \neq E}$. That makes sense to me, since the latter is limited to strictly linear exponents and therefore is limited to linear reductions, not polynomial ones in general.  
> **username_0**: @Emil However, I could really use a link to something explaining why $\mathrm{EXPTIME}$ is not closed under exponential reductions. Intuitively, if I multiply the steps an algorithm takes by an exponential, and it already took an exponential number of steps, I get something like this: $2^{n} \times 2^{n} = 2^{2 \times n}$. So why can I not take an algorithm for a problem in $\mathrm{EXPTIME}$, apply an exponential reduction to it, and have an algorithm that solves another problem in $\mathrm{EXPTIME}$, even if I use that reduction in each step?  
> **username_3**: 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}}$.  

---

## 1 answers

### Answer by username_5 on 2018-11-02. Score: 11

I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and [there is an oracle](https://bibbase.org/network/publication/beigel-buhrman-fortnow-npmightnotbeaseasyasdetectinguniquesolutions-1998) 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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_5**: 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.  
> **username_0**: 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.  

---

