2
$\begingroup$

Forgive me if this problem is known by another name, I do not know any references for it.

Symmetric deduction. An equation $e \in E$ is a subset of variables $V$ such that knowing $|e| - 1$ of the variables allows you to deduce the missing one.

Minimal cover under symmetric deduction. Does there exist a set of $k$ variables such that their closure under symmetric deduction with equations $E$ equals all variables $V$?

This problem is proven NP-complete in this question. There is a limited version of this problem:

Minimal cover under symmetric $d$-deduction. Same as before, except $\forall e\in E: |e| \leq d$. That is, each equation has degree $d$ or lower.

This problem is trivial for $d = 2$ (choose one variable per connected component), and NP-hard for $d = 4$ as shown by Thinh D. Nugyen here.

What about $d = 3$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.