wiki_research

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

1_or_3_in_3_sat (551B)


      1 # 1-or-3-in-3SAT
      2 
      3 The *1-or-3-in-3SAT* [decision_problem] is the variant of [Boolean_satisfiability] where each [clause] contains exactly 3 [literals] and where the [decision_problem] asks whether there exists a [Boolean_valuation] such that each [clause] contains exactly 1 or 3 [literals] that evaluate to true
      4 
      5 This [decision_problem] is in fact in [PTIME] because it is [affine]
      6 
      7 https://cstheory.stackexchange.com/questions/53268/complexity-of-1-or-3-in-3-sat-odd-3-sat
      8 
      9 Up: [schaefers_dichotomy_theorem], [sat_variants]
     10 
     11 Aliases: 1 or 3 in 3SAT