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 known connection between constructive arguments that replace probabilistic methods and derandomization in complexity theory?

(2) Do the same barrier that are hurdles to derandomization play a role in limiting progress in constructive mathematics (where constructive mathematics is as within the scope here)?

(3) Can every such existence proof in probabilistic methods be derandomized?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.