wiki_research

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

3sat_3_occurrences (442B)

      1 # 3SAT 3 occurrences
      2 
      3 [3SAT] where each variable occurs at most 3 times:
      4 
      5 - do you have exactly 3 literals per clause, or at most 3 literals per clause?
      6   - if 3 literals per clause:
      7     - [3SAT_3_occurrences_exactly3] ([PTIME])
      8     - note: if you go beyond [3SAT] and allow larger clauses, then it is still [NP_complete]: cf [tovey1984simplified]
      9   - if at most 3 literals per clause:
     10     - [3SAT_3_occurrences_atmost3]
     11 
     12 Up: [3sat_variants]