The Fooling-Set-Submatrix problem takes integers n,m and an m× m 0/1-matrix A as input, and asks whether A contains a fooling-set submatrix of size n. NP-hardness conjecture. The Fooling-Set-Submatrix problem is NP-hard. The computational complexity of this problem is stated to remain open in the source.

NP-hardness of the Fooling-Set-Submatrix problem

The problem asks whether a given Boolean matrix contains a fooling-set submatrix of a prescribed size. The conjecture is no longer open: Shitov’s 2013 work gives a reduction from Independent Set.

2013 reduction

Shitov constructs a Boolean matrix from a graph such that its maximum fooling-set size equals $|E|+\alpha(G)$ , where $\alpha(G)$ is the maximum independent-set size. Thus the threshold decision problem is NP-hard; the paper also states that it is in NP, hence NP-complete. Later papers independently describe this as an established NP-hardness result and cite the same work.

Current status (as of August 2026): NP-hardness is settled by Shitov’s reduction, and the corresponding decision problem is stated to be NP-complete; no unresolved objection or competing status was found.

Proof (published by Shitov in 2013)

This conjecture was resolved by Yaroslav Shitov in On the Complexity of Boolean Matrix Ranks. Here is the reduction.

Let $G=(V,E_G)$ be a simple undirected graph, and replace every undirected edge by its two orientations. Denote the resulting directed-edge set by $\vec E$ .

Construct a Boolean matrix $A(G)$ whose rows and columns are indexed by the disjoint union $V\sqcup\vec E$ . For vertices $x,y$ and directed edges $e,f$ , define:

$A_{x,y}=1$ exactly when $x=y$ or $x$ and $y$ are adjacent in $G$ ;
$A_{x,e}=1$ exactly when $x$ is the tail of $e$ ;
$A_{e,y}=1$ exactly when $y$ is the head of $e$ ;
$A_{e,f}=1$ exactly when $e=f$ .

I claim that

\operatorname{fool}(A(G))=|\vec E|+\alpha(G),

where $\alpha(G)$ is the independence number.

For the lower bound, let $U\subseteq V$ be independent. Select the diagonal positions

\{(u,u):u\in U\}\cup\{(e,e):e\in\vec E\}.

These form a fooling set. Two distinct vertex diagonals are compatible because $U$ is independent; two distinct edge diagonals have zero cross-entries; and a vertex diagonal and an edge diagonal cannot have both cross-entries equal to $1$ , since that would make the vertex both the head and tail of a loop. Thus

\operatorname{fool}(A(G))\geq|\vec E|+|U|.

For the upper bound, fix $e=(u,v)\in\vec E$ . The four positions in

\{u,e\}\times\{v,e\}

form an all-one rectangle. Every non-vertex-diagonal one-entry of $A(G)$ belongs to exactly one such rectangle. A fooling set can contain at most one position from each all- one rectangle, so it contains at most $|\vec E|$ non-vertex-diagonal positions.

Its remaining positions are vertex diagonals $(w,w)$ . Their vertices must form an independent set: if two were adjacent, both corresponding cross-entries would equal $1$ . Hence there are at most $\alpha(G)$ of them, proving the claimed equality.

Therefore, given an Independent Set instance $(G,k)$ , construct $A(G)$ and ask whether it has a fooling set of size

|\vec E|+k.

The construction is polynomial, and the equality above shows that the answer is yes exactly when $\alpha(G)\geq k$ . Existence of a fooling set of at least this size is equivalent to existence of one of exactly this size, since every subset of a fooling set is again a fooling set.

Thus Fooling-Set-Submatrix is NP-hard. In fact it is NP-complete, because a proposed fooling set can be checked in polynomial time.

Original conjecture, Conjecture 4.3: https://arxiv.org/abs/1305.2468

Published resolution: https://arxiv.org/abs/1306.1114 https://doi.org/10.1016/j.laa.2013.06.033

NP-hardness of the Fooling-Set-Submatrix problem

Primary source

Progress summary

Solutions 1

Proof (published by Shitov in 2013)