18
$\begingroup$

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, but did not get a satisfactory answer.

$\endgroup$
6
  • 7
    $\begingroup$ (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. $\endgroup$ Jun 17, 2012 at 12:30
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 17, 2012 at 12:38
  • 2
    $\begingroup$ @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.. $\endgroup$
    – aelguindy
    Jun 17, 2012 at 13:01
  • 2
    $\begingroup$ Your question does not say that you restrict problem Q to be inside P. If that is your intent, please edit the question. $\endgroup$ Jun 17, 2012 at 13:27
  • 1
    $\begingroup$ 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] $\endgroup$
    – Neal Young
    Aug 12, 2014 at 2:58

3 Answers 3

10
$\begingroup$

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):

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

$\endgroup$
2
  • $\begingroup$ Could you provide reference for the unconditional lower bound? $\endgroup$
    – Turbo
    Mar 7, 2014 at 22:03
  • 1
    $\begingroup$ added reference. $\endgroup$ Mar 8, 2014 at 3:29
13
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Any deterministic algorithm must make at least $n$ queries in the worst case. $\endgroup$ Jun 18, 2012 at 22:18
  • $\begingroup$ What do you mean by "currently we don't know any non-trivial lower bound proof for any problem in NP (let alone P)" ? $\endgroup$ Jun 19, 2012 at 9:12
  • $\begingroup$ 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? $\endgroup$
    – Jagadish
    Jun 19, 2012 at 17:07
  • $\begingroup$ 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. $\endgroup$ Jun 19, 2012 at 21:44
  • $\begingroup$ Ah, right. I assumed that OP was interested in natural problems. I've edited my answer. $\endgroup$
    – Jagadish
    Jun 20, 2012 at 6:15
6
$\begingroup$

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].

See also Efficient and simple randomized algorithms where determinism is difficult .

$\endgroup$

Your Answer

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

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