It was numerically shown in this paper that the ExactCover problem, given the unique satisfying assignment (USA) assumption, could be solved by an adiabatic quantum algorithm (AQC) in time polynomial in the number of variables.

I would like to understand how hard this problem is for classical algorithms. The authors of the AQC paper claimed the following:

" There is also evidence that this set is hard for classical algorithms. Most of the instances we have generated lie near the “phase transition” for Exact Cover. The phase transition region consists of instances with the number of clauses chosen so that half of the instances have one or more satisfying assignments. For 3-SAT, an NP-complete problem closely related to Exact Cover, there is evidence that the hard instances for classical algorithms are located at the phase transition."

This argument is not very convincing to me. I know ExactCover is NP-complete, but is there any paper on the hardness of ExactCover+USA?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.