<p><strong>Problem</strong>: An array $A[1..2n]$ consists of $n$ 1s and $n$ 0s. Find an $i$ such that $A[i]$ is 1. </p>

<p>You are allowed to query 'Which number is present in $A[i]$'? Each query takes constant time. </p>

<p><strong>Solution</strong>: 
Randomized Algorithm: Pick a random index $i$ and check if $A[i]$ is 1. Expected number of queries is 2, but any deterministic algorithm must make at least $n$ queries. Therefore, the randomized upper bound is strictly better than the deterministic lower bound in this model.</p>

<p>This is an example from query complexity which Tsuyoshi was referring to in the comment. </p>

CC BY-SA 3.0
2012-06-18T22:18:13.757Z
Any deterministic algorithm must make at least $n$ queries *in the worst case*.
argentpepper
CC BY-SA 3.0
2012-06-19T09:12:12.067Z
What do you mean by "currently we don't know any non-trivial lower bound proof for any problem in NP (let alone P)" ?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-06-19T17:07:40.597Z
Perhaps I used the word 'non-trivial' sloppily. I meant 'Currently, we can't prove an unconditional lower bound of $\Omega(n^k)$ for $k>0$ for SAT or any problem in NP'. Is that correct?
Jagadish
CC BY-SA 3.0
2012-06-19T21:44:49.447Z
Well, maybe not for "nice" problems such as SAT; but remember we do have such lower bounds for other problems from the time hierarchy theorems. And the question is not about "nice" problems, but about complexity classes.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-06-20T06:15:43.507Z
Ah, right. I assumed that OP was interested in natural problems. I've edited my answer.
Jagadish
CC BY-SA 3.0
2012-06-18T06:01:05.640Z
2012-06-20T06:17:22.663Z
2012-06-20T06:17:22.663Z
Jagadish
<p><em>Given an $n\times n$ payoff matrix for a zero-sum matrix with payoffs in [0,1], estimate the value of the game within an additive $\epsilon$.</em></p>

<p>This problem has a randomized algorithm that runs in time $O(n\log^2(n)/\epsilon^2)$, which (provably) no deterministic algorithm can match  [<a href="http://scholar.google.com/scholar?cluster=3647150107566098261&amp;hl=en&amp;as_sdt=0,5&amp;as_vis=1" rel="nofollow noreferrer">GK95</a>].</p>

<p>See also <a href="https://cstheory.stackexchange.com/questions/14396/efficient-and-simple-randomized-algorithms-where-determinism-is-difficult">Efficient and simple randomized algorithms where determinism is difficult</a> .</p>

CC BY-SA 3.0
2012-11-24T05:16:20.183Z
2012-11-24T05:22:21.570Z
2017-04-13T12:32:28.743Z
Neal Young
<p>Another example is estimating the volume of a polyhedron in high dimensions. There's an unconditional lower bound on deterministic strategies to approximate the volume to even an exponential factor, but there's an FPRAS for the problem. </p>

<p>Update: the relevant paper is (link to <a href="http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_barany_dcg1987_volume.pdf" rel="nofollow">PDF</a>): </p>

<p>I. Barany and Z. Furedi. Computing the volume is difficult, 
Discrete and Computational Geometry 2 (1987), 319-326. </p>

CC BY-SA 3.0
2014-03-07T22:03:13.850Z
Could you provide reference for the unconditional lower bound?
Turbo
CC BY-SA 3.0
2014-03-08T03:29:34.843Z
added reference.
Suresh Venkat
CC BY-SA 3.0
2012-06-18T15:08:19.110Z
2014-03-08T03:29:27.467Z
2014-03-08T03:29:27.467Z
Suresh Venkat
<p>Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$. </p>

<p>Do we know of any problem $Q \in \mathsf{P}$ such that $Q \in \mathsf{BPTIME}(n^k)$ but $Q \not \in \mathsf{DTIME}(n^k)$? 
Is its non-existence proven?</p>

<p>This question was asked on cs.SE <a href="https://cs.stackexchange.com/questions/2362/problems-in-p-with-provably-faster-randomized-algorithms">here</a>, but did not get a satisfactory answer.</p>

CC BY-SA 3.0
2012-06-17T12:30:37.727Z
(1) BPP(f(n)) is usually denoted as BPTIME(f(n)).  (2) In the computational complexity setting, I believe that this is open.  (Many examples are known in the query complexity and the communication complexity settings.)  (3) If its nonexistence were already proved, then we would already know that P=BPP.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-17T12:38:33.457Z
By the way, in the question on cs.stackexchange.com, you have some misunderstanding about the relation between BPTIME and ZPTIME, and that might be part of the reason you have not received a satisfactory answer.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-17T13:01:14.173Z
@TsuyoshiIto Thanks, I don't agree that if we prove inexistence then we know $P=BPP$, I am restricting the setting to problems in $P$. Maybe, $BPTIME(n^k) \cap P = DTIME(n^k)$, while $BPTIME(n^k) \neq DTIME(n^k)$ in general, am I missing something? Could you also please point out my misunderstanding about $BPTIME$ and $ZPTIME$, maybe I missed a satisfactory answer indeed..
aelguindy
CC BY-SA 3.0
2012-06-17T13:27:48.433Z
Your question does not say that you restrict problem Q to be inside P.  If that is your intent, please edit the question.
Tsuyoshi Ito
CC BY-SA 3.0
2014-08-12T02:58:05.603Z
For approximating the 1-median of a finite metric space with few queries to the distance function, a random point gives a 2-approximation in expectation and a (2+eps)-approx with good probability.  But no deterministic algorithm that queries the distance function $o(n^2)$ times can do better than a 4-approximation.  [ [Chang 2013](http://scholar.google.com/scholar?q=%22A+lower+bound+for+1-median+selection+in+metric+spaces%22)]
Neal Young
<cc.complexity-theory><ds.algorithms><randomized-algorithms><derandomization>
Does randomness buy us anything inside P?
aelguindy
# Does randomness buy us anything inside P?

(Asked by: username_0 on 2012-06-17)

Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$.

Do we know of any problem $Q \in \mathsf{P}$ such that $Q \in \mathsf{BPTIME}(n^k)$ but $Q \not \in \mathsf{DTIME}(n^k)$?
Is its non-existence proven?

This question was asked on cs.SE [here](https://cs.stackexchange.com/questions/2362/problems-in-p-with-provably-faster-randomized-algorithms), but did not get a satisfactory answer.

**Tags:** cc.complexity-theory, ds.algorithms, randomized-algorithms, derandomization

> **Comments:**
> **username_1**: (1) BPP(f(n)) is usually denoted as BPTIME(f(n)).  (2) In the computational complexity setting, I believe that this is open.  (Many examples are known in the query complexity and the communication complexity settings.)  (3) If its nonexistence were already proved, then we would already know that P=BPP.  
> **username_1**: By the way, in the question on cs.stackexchange.com, you have some misunderstanding about the relation between BPTIME and ZPTIME, and that might be part of the reason you have not received a satisfactory answer.  
> **username_0**: @TsuyoshiIto Thanks, I don't agree that if we prove inexistence then we know $P=BPP$, I am restricting the setting to problems in $P$. Maybe, $BPTIME(n^k) \cap P = DTIME(n^k)$, while $BPTIME(n^k) \neq DTIME(n^k)$ in general, am I missing something? Could you also please point out my misunderstanding about $BPTIME$ and $ZPTIME$, maybe I missed a satisfactory answer indeed..  
> **username_1**: Your question does not say that you restrict problem Q to be inside P.  If that is your intent, please edit the question.  
> **username_2**: For approximating the 1-median of a finite metric space with few queries to the distance function, a random point gives a 2-approximation in expectation and a (2+eps)-approx with good probability.  But no deterministic algorithm that queries the distance function $o(n^2)$ times can do better than a 4-approximation.  [ [Chang 2013](http://scholar.google.com/scholar?q=%22A+lower+bound+for+1-median+selection+in+metric+spaces%22)]  

---

## 3 answers

### Answer by username_6 on 2012-06-18. Score: 10 | Accepted answer

Another example is estimating the volume of a polyhedron in high dimensions. There's an unconditional lower bound on deterministic strategies to approximate the volume to even an exponential factor, but there's an FPRAS for the problem.

Update: the relevant paper is (link to [PDF](http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_barany_dcg1987_volume.pdf)):

I. Barany and Z. Furedi. Computing the volume is difficult,
Discrete and Computational Geometry 2 (1987), 319-326.

> **Comments:**
> **username_7**: Could you provide reference for the unconditional lower bound?  
> **username_6**: added reference.  

---

### Answer by username_3 on 2012-06-18. Score: 13

**Problem**: An array $A[1..2n]$ consists of $n$ 1s and $n$ 0s. Find an $i$ such that $A[i]$ is 1.

You are allowed to query 'Which number is present in $A[i]$'? Each query takes constant time.

**Solution**:
Randomized Algorithm: Pick a random index $i$ and check if $A[i]$ is 1. Expected number of queries is 2, but any deterministic algorithm must make at least $n$ queries. Therefore, the randomized upper bound is strictly better than the deterministic lower bound in this model.

This is an example from query complexity which Tsuyoshi was referring to in the comment.

> **Comments:**
> **username_4**: Any deterministic algorithm must make at least $n$ queries *in the worst case*.  
> **username_5**: What do you mean by "currently we don't know any non-trivial lower bound proof for any problem in NP (let alone P)" ?  
> **username_3**: Perhaps I used the word 'non-trivial' sloppily. I meant 'Currently, we can't prove an unconditional lower bound of $\Omega(n^k)$ for $k>0$ for SAT or any problem in NP'. Is that correct?  
> **username_5**: Well, maybe not for "nice" problems such as SAT; but remember we do have such lower bounds for other problems from the time hierarchy theorems. And the question is not about "nice" problems, but about complexity classes.  
> **username_3**: Ah, right. I assumed that OP was interested in natural problems. I've edited my answer.  

---

### Answer by username_2 on 2012-11-24. Score: 6

*Given an $n\times n$ payoff matrix for a zero-sum matrix with payoffs in [0,1], estimate the value of the game within an additive $\epsilon$.*

This problem has a randomized algorithm that runs in time $O(n\log^2(n)/\epsilon^2)$, which (provably) no deterministic algorithm can match [[GK95](http://scholar.google.com/scholar?cluster=3647150107566098261&hl=en&as_sdt=0,5&as_vis=1)].

See also [Efficient and simple randomized algorithms where determinism is difficult](https://cstheory.stackexchange.com/questions/14396/efficient-and-simple-randomized-algorithms-where-determinism-is-difficult) .


---

