|
|
|
|
|
|
by currymesurprise
4819 days ago
|
|
|
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. |
|
|