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.
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.