There are in general simple algorithms for determining S in polynomial time, since it’s just a system of linear equations as in the post. Humans came up with those algorithms, and smart LLMs may be able to recognize the problem type and apply a suitable algorithm in chain-of-thought (with some probability of success).
However, average humans don’t know any linear algebra and almost certainly won’t be able to solve more than a trivial-sized problem instance. Most struggle with the very much simpler “Lights Out” puzzle.
Has anybody tried actual humans or smart LLMs? It would be interesting to know what methods people actually use.
There are in general simple algorithms for determining S in polynomial time, since it’s just a system of linear equations as in the post. Humans came up with those algorithms, and smart LLMs may be able to recognize the problem type and apply a suitable algorithm in chain-of-thought (with some probability of success).
However, average humans don’t know any linear algebra and almost certainly won’t be able to solve more than a trivial-sized problem instance. Most struggle with the very much simpler “Lights Out” puzzle.