wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

satisfiability_unambiguous (329B)

      1 # Unambiguous-SAT
      2 
      3 SAT when you are promised there is at most a unique solution
      4 
      5 https://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem
      6 - if unambiguous SAT has a [ptime] algorithm then [rp] = [nptime]
      7 
      8 https://eccc.weizmann.ac.il//report/2011/151/ rules out some possible improvements
      9 
     10 Up: [sat_variants], [unambiguity]