wiki_research

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

3sat_3_occurrences_atmost3 (478B)

      1 # 3SAT 3 occurrences atmost3
      2 
      3 [3SAT] with at most 3 occurrences of each variable and some clauses may have size <3
      4 
      5 - [3SAT] with 2 or 3 literals by clause and at most 3 occurrences of each variable is [np_hard]
      6   - https://cs.stackexchange.com/questions/48442/3-sat-for-variables-appearing-3-times
      7 - [3SAT] with <= 3 literals by clause and each variable occurs 1 time positively and 2 times negatively is [np_hard]
      8   - Lemma 1 of [yannakakis1981edge]
      9 
     10 Up: [3sat_3_occurrences]