3 ms·
I may be totally mistaken, but doesn't the result depend on X and Y unit (or alternatively on the standard dev of the gaussian) ?
by pierrealexandre 17y ago
I may be totally mistaken, but doesn't the result depend on X and Y unit (or alternatively on the standard dev of the gaussian) ?
- carterschonwald 17y agoGood question, so the heart of smoothed analysis is that you need your problem to have the property that there is some sort of small perturbation you can apply to the input data such that there is accordingly only a similarly small shift to the answer the algorithm computes. Once you have that determined, you then try to show that with high probability the runtime of the algorithm on the randomly perturbed data is polynomial on the input size. So in a certain sense, the strength of smoothed analysis is that by applying a small amount of noise to a problem (which you can sometimes argue is simply the process of solving it with fixed precision etc), you can destroy any fragile counterexamples to a good execution speed. Theres a bit more going on, but thats the basic idea