3
$\begingroup$

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.

  1. If the matrix $A$ has no columns, the current partial solution is a valid solution; terminate successfully.
  2. Otherwise choose a column $c$ (deterministically).
  3. Choose a row $r$ such that $A_{r,c} = 1$ (nondeterministically).
  4. Include row $r$ in the partial solution.
  5. 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$.

  6. 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.

$\endgroup$
3
$\begingroup$

Its worst-case running time is exponential.

By "nondeterministic", this essentially means "try all possibilities".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.