{
  "id": "math/0411167",
  "version": "v1",
  "published": "2004-11-08T15:14:03.000Z",
  "updated": "2004-11-08T15:14:03.000Z",
  "title": "Families of unsatisfiable k-CNF formulas with few occurrences per variable",
  "authors": [
    "Shlomo Hoory",
    "Stefan Szeider"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "(k,s)-SAT is the satisfiability problem restricted to instances where each clause has exactly k literals and every variable occurs at most s times. It is known that there exists a function f such that for s\\leq f(k) all (k,s)-SAT instances are satisfiable, but (k,f(k)+1)-SAT is already NP-complete (k\\geq 3). The best known lower and upper bounds on f(k) are Omega(2^k/k) and O(2^k/k^a), where a=\\log_3 4 - 1 = 0.26.... We prove that f(k) = O(2^k \\cdot \\log k/k), which is tight up to a \\log k factor.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-11-08T15:14:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "unsatisfiable k-cnf formulas",
      "occurrences",
      "upper bounds",
      "variable occurs",
      "np-complete"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math.....11167H"
    }
  }
}