Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM DISTINGUISHED ONES

• INSTANCE: Disjoint sets X,Z of variables, collection C of disjunctive clauses of at most 3 literals, where a literal is a variable or a negated variable in $X\cup Z$.

• SOLUTION: Truth assignment for X and Z that satisfies every clause in C.

• MEASURE: The number of Z variables that are set to true in the assignment.

  
  

• Bad News: NPO PB-complete [284].

• Comment: Transformation from MINIMUM INDEPENDENT DOMINATING SET. Not approximable within $(\vert X\vert+\vert Z\vert)^{1-\varepsilon }$ for any $\varepsilon >0$ [279]. MINIMUM ONES, the variation in which all variables are distinguished, i.e. $X=\emptyset$, is also NPO PB-complete [284], and is not approximable within $\vert Z\vert^{1-\varepsilon }$ for any $\varepsilon >0$ [279]. MINIMUM ONES for clauses of 2 literals is approximable within 2 [210]. MINIMUM WEIGHTED SATISFIABILITY, the weighted version, in which every variable is assigned a nonnegative weight, is NPO-complete [388]. Variations corresponding to three- and four-valued logics have also been considered [145].