The Valiant-Vazirani theorem says that both Unique and Unambiguous SAT are NP-hard under randomized reductions. While this is not NP-hard under the usual defin

The Valiant-Vazirani theorem says that both Unique and Unambiguous SAT are NP-hard under randomized reductions. While this is not NP-hard under the usual definition, modern complexity theorists believe derandomization to be possible to a degree similar to their belief that P is not NP.