News for hackers. Stuff that matters.
Re:Performance of Rust and Dart in Sudoku Solving by currymesurprise on Saturday April 06, 2013 @11:21AM (#5503827)
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.

There are no comments on this comment yet.