wiki_research

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

gt_maj_sat (366B)

      1 # GT-MAJ-SAT
      2 
      3 given a [boolean_formula] in [conjunctive_normal_form], determine if >1/2 of the [valuations] are satisfying
      4 
      5 - [akmal2021majority]: 
      6   - it is [np_complete] for k geq 4
      7   - and in [ptime] for k leq 3
      8 - [tantau2022satisfaction]:
      9   - classification for fixed threshold delta and value k of the [clause_width]
     10 
     11 Up: [maj_sat]
     12 
     13 See also: [tantau2024seven]