7
$\begingroup$

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.

Improve this question
$\endgroup$
24
  • 4
    $\begingroup$ Without looking at the paper, I can say that the threshold for "being worthy of arxiv" is quite low. $\endgroup$
    – Aryeh
    Oct 29, 2018 at 21:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aryeh
    Oct 29, 2018 at 22:47
  • 1
    $\begingroup$ 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? $\endgroup$
    – Michael Wehar
    Oct 29, 2018 at 23:09
  • 4
    $\begingroup$ 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? $\endgroup$
    – Emil Jeřábek
    Oct 30, 2018 at 13:26
  • 2
    $\begingroup$ 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}}$. $\endgroup$
    – Emil Jeřábek
    Nov 4, 2018 at 11:09

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Jake Thomas
    Nov 3, 2018 at 23:45
  • $\begingroup$ 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. $\endgroup$
    – Jake Thomas
    Nov 4, 2018 at 0:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – Lance Fortnow
    Nov 4, 2018 at 13:29
  • $\begingroup$ 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. $\endgroup$
    – Jake Thomas
    Nov 4, 2018 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.