灯泡通断问题：
你得到的开关少，灯泡少，不一定相等，每个按钮可以连接到多个灯泡，当一个开关被打开时，它打开已经关闭的灯泡，关闭已经打开的灯泡我们需要找到是否所有的灯泡都可以通过开关这些开关点燃？
我们可以在O（2 ^ n.n.x）（n，开关的数目；m，总灯泡；x，任何开关接通的灯泡的最大数目）上强力地解决这个问题。在这里，我们尝试开关o（2^n）的所有组合，并在从所选开关o（n.x）打开所有灯泡后检查是否所有灯泡都在o（m）上
这可以在非指数时间内完成吗，也许是一个启发式的。
这有点涉及集合打包和集合覆盖问题，并且两者似乎都只有近似算法（NP-hard，IrrC）。
最佳答案
答案是“是”，你可以在O（m in（（m^2）n，（n^2）m））时间内解决这类难题。
你的问题可以看作是整数mod 2的matrix，其中乘法变成布尔“and”，加法变成布尔“xor”。
使事情更具体：可以将“原始”灯泡状态（所有开关都关闭）表示为布尔列向量，将每个开关的状态表示为另一个布尔向量，将每个开关切换的灯泡集表示为布尔矩阵的相应列：
output original matrix switches
[v] [u] [m m m m m m] [x]
[v] = [u] + [m m m m m m] * [x]
[v] [u] [m m m m m m] [x]
[x]
[x]
这是一组整数mod 2下的线性方程组，您可以使用标准linear equation solvers的适当修改版本有效地解决此类问题。
请注意，这样做的原因是，拨动开关总是切换同一组灯泡如果不是这样，那么方程就不是线性的，你不能用这种方法求解。一般来说，如果你在这类问题中有“或”和“和”的混合，你很可能会有一些变化的"SAT" problem，这是np完全的。