Questions tagged [probabilistic-method]

Probabilistic methods prove existence results in a nonconstructive fashion, by showing the chance of randomly selecting a solution is greater than zero.

Filter by
Sorted by
Tagged with
3 votes
0 answers
236 views

Derandomization barriers in complexity theory applicable as barriers to constructive arguments replacing probabilistic method

The probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object while finding that object may take exponential time. (1) Is there any ...
Turbo's user avatar
  • 13.7k