Assume $P\neq BPP\neq NP$ with caveat that there is a deterministic algorithm for every $NP$ complete problem with input size $n$ bits in $2^{(\log n)^{1+f(n)}}$ arithmetic operations on $\log n$ sized words where $f(n)$ grows slower than any definable function.

Where does complexity of intermediate problems stand in this case and utility of randomness stand in this case?

What is scenario if $P= BPP\neq NP$ or $P\neq BPP=NP$ holds?

  • 3
    $\begingroup$ Why don't you focus on 1 question instead of 3? I am not sure they are related enough. First, I would not ask about the 2nd case P=BPP≠NP because that is the expected scenario (certainly not the worst one for most people). Also, in the 3rd case, do you mean P≠BPP while P=NP? If so, that would be an interesting case but it looks almost opposite to P≠BPP≠NP. $\endgroup$ – Juan Bermejo Vega Sep 5 '15 at 12:51
  • 5
    $\begingroup$ Not a well thought out question. Is there a function that grows slower than all "definable" functions? Definable in where? Etc. As has been said numerous times, you need to spend more time thinking about your questions before posting them. Also you should explain why you care about the answer. $\endgroup$ – Kaveh Sep 7 '15 at 0:21
  • 3
    $\begingroup$ A reasonable question would be about the complexity of NPI problems if $P\subset NP \subseteq(DTime(f))$ where $f$ is barely super polynomial. But the answer seems obvious: they would be outside P but strictly inside $DTime(f)$. What would you like to know in addition to that? Not clear. $\endgroup$ – Kaveh Sep 7 '15 at 0:30
  • 4
    $\begingroup$ ps: I think the low quality of your questions is a result of not really caring about them in the sense that you typically do not spend enough time trying to answer them yourself before posting them here. $\endgroup$ – Kaveh Sep 7 '15 at 0:33
  • 5
    $\begingroup$ I still think this is a low quality question. Also you make things unnecessarily convoluted without any clear reason. E.g. why do you use a different model from the one that is used to define these classes (arithmetic operations on log n size words)? Unclear. Do you know if there exists any $f$ with the property you describe? Unclear. Why not simply say $f$ is barely superpolynomail like $n^{\lg^* n}$? Unclear. ... Adding a question about BPP on top these as an after though doesn't improve the question. I think this question should be closed for multiple reasons. $\endgroup$ – Kaveh Sep 7 '15 at 20:03

The complexity of intermediate problems stands everywhere, since that case is impossible.

Let $b$ be the base of $\log$. $\:$ (It's probably $2$ or $e$, but it's value isn't important.)

For all $n$, if $\: b < n \:$ then $$2^{\hspace{.02 in}(\hspace{.02 in}\log(n))^{1+\frac1{\log(\log(n))}}} \; = \; 2^{\left(\hspace{-0.03 in}(\hspace{.02 in}\log(n))^1\hspace{-0.02 in}\right) \cdot \left(\hspace{-0.06 in}(\hspace{.02 in}\log(n))^{\frac1{\log(\log(n))}}\hspace{-0.03 in}\right)} \; = \; 2^{\hspace{.02 in}\log(n) \cdot \left(b^{\hspace{.02 in}\log(\log(n))\hspace{.03 in}}\right)^{\frac1{\log(\log(n))}}} \\ = \; 2^{\hspace{.02 in}\log(n) \cdot b^{\hspace{.02 in}\log(\log(n)) \cdot \frac1{\log(\log(n))}}} \; = \; 2^{\hspace{.02 in}\log(n) \cdot b^1} \; = \; 2^{\hspace{.02 in}\log(n) \cdot b} \; = \; \left(b^{\hspace{.02 in}\log(2)}\hspace{-0.04 in}\right)^{\hspace{.02 in}\log(n) \cdot b} \; \\ = \; b^{\hspace{.02 in}\log(2) \cdot \log(n) \cdot b} \; = \; b^{\hspace{.02 in}\log(n) \cdot \log(2) \cdot b} \; = \; \left(b^{\hspace{.02 in}\log(n)}\hspace{-0.04 in}\right)^{\hspace{.02 in}\log(2) \cdot b} \; = \; n^{\hspace{.02 in}\log(2) \cdot b}$$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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