wiki_research

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

2sat (363B)

      1 # 2SAT
      2 
      3 The [satisfiability_boolean] problem over [2CNF]
      4 
      5 It is tractable:
      6 - Can be solved in [linear_time] via [strongly_connected_components]
      7 - Is [nl_complete]
      8 
      9 However:
     10 
     11 - [MAX_2SAT] is [NP_hard]
     12 - The [sharp_satisfiability] problem of counting the satisfying assignments is [NP_hard] even for [monotone2cnf]
     13 
     14 See also: [3sat], [Max_2sat]
     15 
     16 Up: [sat_variants]