Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?

cs.stackexchange https://cs.stackexchange.com/questions/79947

문제

Input: amount of variables (with minimum of $10$ since otherwise problem is unsolvable).

Output: unsatisfiable formula.

Restrictions:

  1. Every clause contains exactly 3 variables.
  2. Every clause differs by at least one variable. For example, a pair of clauses $(x\lor y\lor z)\land(x\lor \overline y\lor\overline z)$ is forbidden.
  3. Every variable must be involved.
  4. Removing any clause makes the formula satisfiable.

No set of clauses is given as input. Is this problem in $\mathsf{FP}$ or is it $\mathsf{NP}$-hard?

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top