patternMinor
Is it possible to prove $\mathsf{BPP = NP}$ statistically?
Viewed 0 times
mathsfstatisticallypossibleprovebpp
Problem
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}$?
Solution
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).
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).
Context
StackExchange Computer Science Q#76507, answer score: 3
Revisions (0)
No revisions yet.