Assuming that someone will find poly-time algorithm that statistically is wrong on ~1% of total (already runned) instances (which are very different), will it be a proof for $\mathsf{BPP = NP}$?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ A poly-time algorithm for what problem? 1%, measured how? The space of all possible inputs is infinite, so it's tricky how to define what it means for one infinite set to be 1% of another infinite set. In other words, the question doesn't seem well-posed/well-specified yet. Can you edit it to clarify what you are asking? $\endgroup$– D.W. ♦Jun 8, 2017 at 18:25
-
$\begingroup$ @D.W., well, statistically usually meant that it's true for already known infomation. Of course, if someone prove it for infinite set, it would be mathematical proof for $\mathsf{BPP = NP}$. $\endgroup$– rus9384Jun 8, 2017 at 20:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
One way to interpret your statement is:
Suppose that $\mathsf{L\in NP}$, and there exists a polynomial time deterministic algorithm $A$ such that for all $n$: $\Pr\limits_{x\sim U_n}\left[ A(x) = L(x)\right]\ge 0.99$, where $U_n$ is the uniform distribution over $\{0,1\}^n$, does this imply $\mathsf{L\in BPP}$?
As Yuval mentioned, the question (at heart) relates to the difference between randomized complexity and distributional (average case) complexity. Randomized complexity is the time required to correctly decide the membership of all inputs with high probability (where the probability is over the inner randomness of the algoirthm), whereas average case complexity is the time required for a deterministic algorithm to correctly decide "most" instances (relative to some distribution $\mathcal{D}$ over possible inputs).
This means that the question translates to whether the worst case hardness of an NP problem implies its average case hardness (the opposite direction is a result of Yao's principle, see this question for details). To the best of my knowledge, this is an open problem. There are many works on the subject, e.g. On Worst-Case to Average-Case Reductions for NP Problems by Andrej Bogdanov and Luca Trevisan. The paper defines what it means for a language to have a worst to average case reduction, and shows that unless the polynomial hierarchy collapses, such reductions cannot exist for NP complete problems (the implication might still hold, but not through their form of reduction).
$\begingroup$
$\endgroup$
7
Both $\mathsf{BPP}$ and $\mathsf{NP}$ are worst-case complexity classes. A problem belongs to one of these classes if there is a polynomial time algorithm (probabilistic or non-deterministic) which works correctly on all instances.
When talking about average-case complexity, you have to specify an input distribution. Some problems and input distributions are self-reducible: if you can solve 99% of the instances correctly (where 99% is measured according to the input distribution), then there is a probabilistic algorithm which solves any given instance correctly with probability 99% (the probability is now only on the coin tosses of the algorithm). In such cases there is no difference between average-case performance and worst-case performance.
answered Jun 8, 2017 at 12:44
-
$\begingroup$ Doesn't $\mathsf{BPP}$ mean bounded error probabilistic polynomial time? So, that means that first attempt of randomized algorithm can be wrong with some chance < 50%. So, adding randomization to such algorithm can make the output correct (after polynomial or subpolynomial amount of it's runs). $\endgroup$– rus9384Jun 8, 2017 at 13:18
-
$\begingroup$ Unfortunately, while it is conjecture that $\mathsf{P} = \mathsf{BPP}$, we don't know that this holds. It is true that you can reduce the error significantly by repeating the algorithm many times and taking a majority vote. $\endgroup$ Jun 8, 2017 at 13:19
-
$\begingroup$ But well, if correctness is statistically 99% for, let's say, graph coloring, it means that $\mathsf{BPP = NP}$ or not? Although, in such case it's possible that $\mathsf{RP = NP}$ since I have no idea how to make error two-sided (it shouldn't be artificial). $\endgroup$– rus9384Jun 8, 2017 at 13:28
-
1$\begingroup$ This is a meaningless questions, since for every instance we can create an algorithm that works on that particular instance. In worst-case complexity, we are looking for algorithms that work on all inputs. In average-case complexity, we are interested in algorithms that work on most inputs, where most is with respect to a given probability distribution. $\endgroup$ Jun 8, 2017 at 13:51
-
2$\begingroup$ Of course, what I meant is not the the question is meaningless, but rather that the concept of a worst-case instance (not within the context of a specific algorithm) is meaningless. $\endgroup$ Jun 8, 2017 at 14:35