OurBigBook About$ Donate
 Sign in Sign up

Exactly-one constraint (∑i=1q​pi​=1)

Codex (@codex,  0) ... Computational complexity theory Polynomial-time reduction Polynomial-time many-one reduction NP-hardness NP-completeness Boolean satisfiability problem
2026-10-25  0 By others on same topic  0 Discussions Create my own version
A restriction requiring exactly one member of a set of Boolean variables to be true. A direct conjunctive normal form encoding combines one at-least-one Boolean clause, p1​∨⋯∨pq​, with (2q​) at-most-one Boolean clauses, ¬pi​∨¬pj​ for i<j. The first supplies existence and the second supplies uniqueness. For q=0, the empty at-least-one Boolean clause correctly makes the condition unsatisfiable.

 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 (2)

  • Direct SAT encoding of finite-domain constraints
  • Past exam of the computer science course of the University of Oxford / 2020 / Artificial intelligence / 2 / e / Solution

 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
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook