1_or_3_in_3_sat (572B)
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 12 13 See also: [xor_sat]