2
$\begingroup$

Problem

Given a search algorithm that can be used to query a k-dimensional space, produced from an input array of N data, has a time complexity of $O(klog^2N)$. This algorithm partitions the space into four regions then selects three of those regions due to some condition. From there it selects at random one of the three spaces as the next space to check for the answer. If this algorithm produces a value it is 100% the correct solution, else it states it cannot find the solution which is always wrong because the item being searched is always there. Therein, the theory is to run it a bunch of times until it produces the solution.

Question

I created this algorithm which is to be utilized as an experiment to create a BPP algorithm for a data analysis problem. But, I am uncertain if it qualifies as a BPP algorithm. From my understanding it is not, because it has a one in three chance of selecting the correct partition at each time it partitions the space. This means the probability of selecting the correct solution is $(1/3)^{klogN}$ making the probability of selecting the incorrect solution one minus the probability of the correct solution.

So, my question is A) Is my interpretation correct for measuring the probability? B) Does this algorithm qualify as a BPP algorithm or some other class?

$\endgroup$
  • $\begingroup$ "[...] it produces no solution which is always wrong for my problem space." Is this supposed to mean the algorithm at times produces no solution and this is wrong for the problem space (since there is always a solution)? or, rather, that the algorithm does not produce a solution which is "always wrong"? $\endgroup$ – dkaeae Mar 6 at 17:43
  • $\begingroup$ The search algorithm indicates it cannot find the answer which is wrong because the item is always in the space. $\endgroup$ – tkellehe Mar 6 at 17:44
  • 1
    $\begingroup$ Wait... So there is always a solution? How is this not trivial as a decision problem? Otherwise, if you are referring to search problems, then you should not be talking about BPP at all (since BPP is a class of decision problems), but rather about two-sided, one-sided, or zero-sided error. $\endgroup$ – dkaeae Mar 6 at 17:47
  • $\begingroup$ Essentially it used some subset of the input array of size N to produce each entry in the k-dimensional space and once you find it in that space you find what subset was used to create it. It is not necessarily useful problem just me playing around with this data and making algorithms for it :) $\endgroup$ – tkellehe Mar 6 at 17:50
  • 1
    $\begingroup$ As I have said, BPP deals only with decision problems. The output is simply "yes" or "no". In your case, there is always a solution, so the decision problem is trivially solvable by always outputting "yes". What you actually have is a Las Vegas algorithm: It always produces correct answers, although (with small probability) it may also fail to find one. $\endgroup$ – dkaeae Mar 6 at 17:58
2
$\begingroup$

The class BPP (and related classes such as RP, coRP, and ZPP) deal with decision problems. This means the algorithms corresponding to these classes may only produce "yes" or "no" answers. This notion does not quite match your algorithm, which is actually solving a search problem (i.e., the solution set is a subset of some arbitrary set of outputs).

At any rate, what you are actually trying to refer to as a "BPP algorithm" is a randomized algorithm with two-sided error. Such an algorithm produces correct and incorrect answers for both instances that have and do not have a solution, and, usually, it is also required that the algorithm be correct "most of the time" (where this is defined by bounding the error by some probability constant).

However, your algorithm has not actually two-sided nor one-sided error. This is because your problem instances all have solutions (and your algorithm does not claim otherwise). Thus, your algorithm only really fails to find solutions with some probability, which makes it have zero-sided error, that is, it always outputs correct answers, but may also output a "could not find" or "don't know" answer (with some bounded probability). As a result, what you have is a Las Vegas algorithm, which is a type of probabilistic algorithm with applications well beyond complexity theory. Incidentally, the alternative definition for a Las Vegas algorithm (i.e., a probabilistic algorithm with expected polynomial time complexity) is quite consistent with your remark that you need to run your algorithm "a bunch of times until it produces the solution."

On a side note, the complexity class associated with decision problems solvable with zero-sided error probabilistic TMs is the class ZPP (though this is only tangential to your question since, as I have explained above, you are not working in the realm of decision problems anyway).

$\endgroup$
1
$\begingroup$

The definition of BPP is that the algorithm always runs and finishes in polynomial time, and the probability it makes an error is $\le 1/3$. So, apply that to your algorithm. You told us it completes in polynomial time, so it meets that condition. Next you must figure out if the error probability is at most $1/3$. If your algorithm runs the search process once, the answer is no: the error probability is $2/3$, which is too large. However, if your algorithm repeats the search process three times and output the first value it finds, then the probability it makes an error is $(2/3)^3 \approx 0.296 \le 1/3$, so repeating it three times gives you an algorithm that is in BPP. (Of course, if you repeat three times, the running time will still be polynomial.)

Strictly speaking BPP only applies to decision problems, that check whether the input is a member of a language or not, and your problem isn't phrased in those terms. However your situation is close enough that if you said "my algorithm is in BPP" theorists would understand what you meant.

$\endgroup$
  • $\begingroup$ Except the OP's algorithm does not really produce wrong answers... (See comments.) If anything, it is closer to a ZPP algorithm than a BPP one. $\endgroup$ – dkaeae Mar 6 at 22:59
  • $\begingroup$ @dkaeae, yeah, your answer is helpful, too! I interpreted the output of the algorithm as "yes a solution exists" or "no a solution doesn't exist", so if it outputs the latter, it produced a wrong answer. But you're absolutely right that strictly speaking it doesn't fit into the definition of BPP and decision problems; I agree. $\endgroup$ – D.W. Mar 7 at 0:23
  • $\begingroup$ @D.W., After looking over this it made me wonder something. Let us say that the algorithm can produce a wrong answer. Why would the error be $2/3$ versus the $(1-(1/3)^{klog{N}})$ as my question shows? $\endgroup$ – tkellehe Mar 7 at 21:04
  • 1
    $\begingroup$ @tkellehe, No reasoning is provided, so I can't tell where your formula comes from. It looks like that might be incorrect; it appears that it might be mixing up the number of times we iterate the search process (each partition) vs the time to perform one iteration of the search process (a single partition). But I can't tell for sure because the justification behind that calculation is not clear to me. $\endgroup$ – D.W. Mar 7 at 21:13
  • $\begingroup$ @D.W., Oh! I was calculating based off of partitioning until it found a single item that is either what I was looking for or not. But what you are saying is for the single decision of picking the correct partition is 1/3. That makes more sense, thank you. $\endgroup$ – tkellehe Mar 7 at 22:47

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.