Knuth's Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that solves the NP-complete problem exact cover (EC). (It actually finds all solutions to EC.)
I do not understand how such algorithm could do that. What is the time complexity of this algorithm in terms of big-O notation?
Here is the algorithm from Wikipedia.
- If the matrix $A$ has no columns, the current partial solution is a valid solution; terminate successfully.
- Otherwise choose a column $c$ (deterministically).
- Choose a row $r$ such that $A_{r,c} = 1$ (nondeterministically).
- Include row $r$ in the partial solution.
For each column $j$ such that $A_{r,j} = 1$,
for each row $i$ such that $A_{i,j} = 1$,
- delete row $i$ from matrix $A$.
delete column $j$ from matrix $A$.
Repeat this algorithm recursively on the reduced matrix A.
Step 3 of the algorithm is done nondeterministically. What does this mean? (I think this is the point why I cannot find the big-O complexity of the algorithm.)
An implementation of Algorithm X in python can be found in Algorithm X in 30 lines! where I cannot find the nondeterministic choice of step 3.