A Boolean formula is in disjunctive normal form when it is a disjunction of conjunctions of Boolean literals. Width bounds the number of literals in each conjunction, not the number of conjunctions. A depth- decision tree gives such a formula of width at most by taking the disjunction of its accepting leaf conditions; rejecting leaves give the dual conjunctive normal form.

Ancestors (10)

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

Synonyms (1)

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