3-SAT is the Boolean satisfiability problem restricted to Boolean formulas in conjunctive normal form with at most three Boolean literals per Boolean clause. It is NP-complete. A nonempty short Boolean clause can be padded to three positions by repeating a Boolean literal, without changing satisfiability.

Ancestors (9)

  1. Boolean satisfiability problem
  2. NP-completeness
  3. NP-hardness
  4. Polynomial-time many-one reduction
  5. Polynomial-time reduction
  6. Computational complexity theory
  7. Theoretical computer science
  8. Computer science
  9. Home

Incoming links (6)

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version