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

<p>Where does complexity of intermediate problems stand in this case and utility of randomness stand in this case?</p>

<p>What is scenario if $P= BPP\neq NP$ or $P\neq BPP=NP$ holds?</p>

CC BY-SA 3.0
2015-09-05T12:51:24.127Z
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.
Juan Bermejo Vega
CC BY-SA 3.0
2015-09-05T12:59:41.280Z
All three are distinct cases of same problem. In all $P\neq NP$ however status of $BPP$ changes w.r.t to enclosing classes.
Turbo
CC BY-SA 3.0
2015-09-07T00:21:55.260Z
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.
Kaveh
CC BY-SA 3.0
2015-09-07T00:30:53.040Z
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.
Kaveh
CC BY-SA 3.0
2015-09-07T00:33:33.220Z
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.
Kaveh
CC BY-SA 3.0
2015-09-07T18:44:15.830Z
@Kaveh I think this is a perfectly valid question. We know $2^{(\log n)^2}$ algorithm is possible. In Ricky's answer $b$ still grows, so it is not a polynomial in $n$ as one may naively think. I do not understand why he says it is impossible. It seems perfectly possible to me.
Turbo
CC BY-SA 3.0
2015-09-07T19:01:27.063Z
As you say it is between $P$ and something that grows as slowly fast as you can(not) imagine faster than $P$. What is the place for NPI then (also randomness)?
Turbo
CC BY-SA 3.0
2015-09-07T20:03:27.190Z
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.
Kaveh
CC BY-SA 3.0
2015-09-07T23:01:01.013Z
@Kaveh I do not think $log^*n$ is slow enough since NPI problems could lie between $n^c$ and $n^{\log^*n}$. This is more nuanced.
Turbo
CC BY-SA 3.0
2015-09-08T06:32:47.540Z
$b$ does not grow in your answer which is clearly not I seek. Your interpretation reduces to Kaveh's interpretation (both are equivalent). Whole point of my post is what happens when we cannot define what is in between poly time $n^c$ and assumed complexity of NP complete problems in post which is $2^(log n)^(1+f(n))$. In this case how do you interpret NPI (under ladner's theorem) and randomness under different scenarios?
Turbo
CC BY-SA 3.0
2015-09-10T22:43:25.747Z
@Turbo: It's unclear that $f(n)$ is well-defined, and that makes your question hard to answer. If you instantiate $f(n)$ with any concrete, slightly super-polynomial function then Ladner's Theorem holds (in the TM model).
Huck Bennett
CC BY-SA 3.0
2015-09-10T22:44:59.227Z
@HuckBennett Yes I see that with a fixed definition of $f(n)$. However I feel complexity theory allows such an unclear possibility with my interpretation.
Turbo
CC BY-SA 3.0
2015-09-10T22:51:37.077Z
@HuckBennett Because $NP-P$ problem is ultimately an asymptotic problem. That is why we have this weird possibility.
Turbo
<randomness><derandomization><p-vs-np><conditional-results><np-intermediate>
What is the status of intermediate problems if P is not NP in worst way imaginable?
Turbo
# What is the status of intermediate problems if P is not NP in worst way imaginable?

(Asked by: username_0 on 2015-09-04)

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?

**Tags:** randomness, derandomization, p-vs-np, conditional-results, np-intermediate

> **Comments:**
> **username_1**: 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.  
> **username_0**: All three are distinct cases of same problem. In all $P\neq NP$ however status of $BPP$ changes w.r.t to enclosing classes.  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_0**: @username_2 I think this is a perfectly valid question. We know $2^{(\log n)^2}$ algorithm is possible. In Ricky's answer $b$ still grows, so it is not a polynomial in $n$ as one may naively think. I do not understand why he says it is impossible. It seems perfectly possible to me.  
> **username_0**: As you say it is between $P$ and something that grows as slowly fast as you can(not) imagine faster than $P$. What is the place for NPI then (also randomness)?  
> **username_2**: 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.  
> **username_0**: @username_2 I do not think $log^*n$ is slow enough since NPI problems could lie between $n^c$ and $n^{\log^*n}$. This is more nuanced.  
> **username_0**: $b$ does not grow in your answer which is clearly not I seek. Your interpretation reduces to username_2's interpretation (both are equivalent). Whole point of my post is what happens when we cannot define what is in between poly time $n^c$ and assumed complexity of NP complete problems in post which is $2^(log n)^(1+f(n))$. In this case how do you interpret NPI (under ladner's theorem) and randomness under different scenarios?  
> **username_3**: @username_0: It's unclear that $f(n)$ is well-defined, and that makes your question hard to answer. If you instantiate $f(n)$ with any concrete, slightly super-polynomial function then Ladner's Theorem holds (in the TM model).  
> **username_0**: @HuckBennett Yes I see that with a fixed definition of $f(n)$. However I feel complexity theory allows such an unclear possibility with my interpretation.  
> **username_0**: @HuckBennett Because $NP-P$ problem is ultimately an asymptotic problem. That is why we have this weird possibility.  

---

## 0 answers

