Task 103 - is it NP-Complete?
Back to General discussions forum
Am I right in thinking this problem is NP-complete? It seems to me to be pretty much the same as finding a subset that sums up to a given constant, except here we use XOR instead. Is there some property of XOR that makes solving this problem different from the subset-sum problem? I have a naive DFS solution that solves the problem but is very slow because it is a full tree traversal and will permute the solutions.
I just wanted to check that I have the correct approach, or is there some other way I should be approaching this problem? For the full subset-sum problem I did not see a good dynamic programming method, other than smartly structuring the traversal as to not permute the solutions. I am of course only touching each egg once since A ^ A = 0.
I am writing the full C solution, but I need to make my own set, so it is not quite done. It will be faster because it will not permute the solutions and it has a better heruistic for branching, however at the heart it is still exponential. I just wanted to make sure I am not barking up the wrong tree before I implement this approach fully.
Hi! Thanks for an interesting question!
To be honest I do not know / do not remember well. When I created the problem, I think I've made limits small so that bruteforce should work.
However I think you can regard the problem as the system of linear equations over GF(2). If I am correct
in this, complexity should be about O(N^3) with Gauss method, for example.
E.g. touching an egg is setting Xi to 1 and their resulting colors are Yj. So the mapping which
egg colors which is just a square matrix:
Yj = sum(Aij * Xi, i = 1..N) mod 2
Where Aij is 1 if touching the egg i changes the color of the egg j.
I do not mean I'm ready to write this solution at once :)
You might be overthinking it. It's definitely solvable in polynomial time, so not NP.
With 20 eggs the solution can require you to touch between 1 and 20 eggs, so at most, 2^20 (~1,000,000) possibilities.
The problem is definitely solvable in a few seconds (and I'm using VB... with C I would expect below 1 second).
> With 20 eggs the solution can require you to touch between 1 and 20 eggs, so at most, 2^20
I think the author of the question meant that for N eggs you get O(2^N) complexity which is not polynomial...
Well if I get it right myself :)