Reconciling Quine-McCluskey Algorithm

I'm开发者_StackOverflow社区 looking at the article on wikipdia for this algorithm, and I see two seemingly contradictory statements:

"it also gives a deterministic way to check that the minimal form of a Boolean function has been reached"

and

"has a limited range of use since the problem it solves is NP-hard"

Thoughts?

p.s. Is there a Visual Studio plugin that can reduce conditional logic by applying this algorithtm to highlighted code?

The algorithm takes exponential time. All NP-complete problems can be solved in exponential time. Presumably the problem referred to is NP-complete in addition to being NP-hard.

The discrepancy is probably because you don't fully understand the definition of NP-hard: http://en.wikipedia.org/wiki/NP-hard

There's nothing contradictory in those statements.
You might be confused about what 'deterministic' means in this context:

In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states.

From wikipedia

In this sense, almost all widely used CS algorithms are deterministic.

I'm sure you already know what 'NP-hard' means :)