我正在尝试解决以下问题：

给定一个二进制矩阵和一个向量，是否存在一个二进制向量满足以下要求？$\mathbf{A} \in \{0,1\}^{m \times n}$$\mathbf{b} \in \mathbb N^n$$\mathbf{c} \in \{0,1\}^n$

1. $\mathbf{c}^\top \mathbf{b} < x$，其中是给定的阈值。$x$

2. $\mathbf{c}^\top$是矩阵中行的线性组合。$\mathbf{A}$

到目前为止，我的尝试集中在构建所有可能的二元向量，维度为，检查所有这些向量的要求编号 1，然后检查满足要求编号 1 的所有向量的要求编号 2。这种蛮力方法由于 n 和 m 可以变得相当大，因此已经非常无效。$1\times n$

我怎样才能以比我的蛮力方法更有效的方式解决这个问题？

用一个虚构的例子说明了这个问题：

假设公司内的员工可以自由地请求该公司内各部门组的汇总收入数据。人的组的总收入时，才会批准请求。检查每个请求的组本身是否满足此要求是微不足道的。但是，可以请求多个组，因此还必须进行检查以确定组合的组是否可以识别少于人的组的收入。$x$$x$

在这个例子中，矩阵和向量可以解释如下：

矩阵A：每一行代表一个请求的组，每一列代表一个部门。值“1”表示部门包含在组中，“0”表示不包含。

向量 b：包括有关每个部门有多少员工的信息。

因此，满足这两个要求的二进制向量的存在意味着应该拒绝对数据的请求。

我决定包括这个例子，以防我对问题的解释有缺陷或只是不必要的限制。非常感谢所有帮助。

编辑：

作为一个例子，我选择设置并定义和如下：$x = 4$$A$$b$

$$A = \begin{pmatrix}1 & 1 & 1 \\\ 0 & 1 & 0 \\\ 0 & 0 & 1\end{pmatrix}\ \ \ \ \ \ \ \ \ b = \begin{pmatrix}2 \\\ 5 \\\ 7 \end{pmatrix}$$

如上所述，矩阵表示请求的部门（列）组（行）。向量包含有关每个部门有多少员工的信息。在此示例中，很明显，所有请求的组本身都将满足条件，即它们没有识别少于四个人的组的总收入。我们可以通过计算来检查：$A$$b$

$$Ab = \begin{pmatrix} 14 \\\ 5 \\\ 7\end{pmatrix}$$

我们看到所有组中有五名或更多员工。但是，如果我们在矩阵中从第一行中减去第二行和第三行，我们可以看到我们可以在矩阵的第一列中确定部门的总收入。该部门只有两名员工，因此请求组的线性组合允许识别只有两个人的组的总收入！这意味着应拒绝对这些部门组的请求。此示例产生作为以下二进制向量，它满足两个条件：$A$$A$$c^T$

$$c^T=\begin{pmatrix} 1 & 0 & 0\end{pmatrix}$$

中删除第三行，那么满足这两个条件的二进制向量将不存在。$A$$c^T$