1
$\begingroup$

I can not find a solution to the following problem. The problem is:

We have an algorithm A for a decision problem that answers yes or no and for every input it gives the right answer with possibility at least equal to q. To improve the possibility q, we run the algorithm 3 times and we see the three outputs. Which is the possibility for the answer to be true? Is this possibility indeed higher than q?

thank you.

  • 0
    This has been studied in the literature on _fault-tolerant computing_. Search for _triple modular redundancy_, which uses three (possibly faulty) identical circuits to evaluate a Boolean function, and takes a majority vote of the three outputs to decide the correct value. See e.g. [here](http://courses.engr.illinois.edu/ece313/fall00/ppt/Lecture19.pdf) for a simple example that leads to the same answer as given by Ansgar Esztermann, and which also considers failures in the majority computation. It is not how people vote, but how ballots are counted, that determines the results of elections.2012-02-07

1 Answers 1