Re:The N-Queens completion problem is NP-hard
by ritinkar on Monday September 04, 2017 @05:29PM
(#15170969)
Isn't 2^n an exponential algorithm. I thought NP algos are still n^k but non-deterministic.
Re:The N-Queens completion problem is NP-hard
by johncolanduoni on Tuesday September 05, 2017 @01:06AM
(#15172666)
When we talk about the big-O for a given problem, the default interpretation is for a deterministic computer. All of our existing deterministic algorithms for NP-complete problems are exponential, and solving an NP-complete problem like SAT on a non-deterministic computer is trivial (and not especially useful since we don't know how to build those).
Re:The N-Queens completion problem is NP-hard
by umanwizard on Monday September 04, 2017 @07:15PM
(#15171429)
A decision problem (i.e., determining whether a string is a member of some set) is in NP if there is a program and polynomials p and q such that for every string x in the set, there is some proof of that fact of size at most q(|x|), which the program can verify is correct in time at most p(|x|).
This implies that there exists an exponential-time deterministic algorithm to solve any NP problem: just check all the possible proofs, reporting "yes" if you find one that works, or "no" when you've generated all the proofs size q(|x|) and found that they fail.
When Computer Scientists talk about "fast" they generally mean that an algorithm is solvable in `n^k` steps, with `n` being based on the size of the input (1000 or 1000000 in your example) and `k` being a constant. Algorithms that follow that rule are called Polynomial, or P for short.
A lot of problems require more steps (e.g. `2^n` steps) as far as we know, but if you have a solution to the problem you can easily (with a P algorithm) verify that it is the correct solution. These are called NP problems.
One of the biggest questions in Computer Science is whether all NP problems also have a P algorithm (P=NP), or whether some problems will always require NP time (P≠NP)
This doesn't have a direct relation with "real" computer time (with modern computers a `2^n` algorithm is quite usable if your n is small enough), but it does mean that once your n becomes large enough and your problem is in NP, you can basically forget about finding an exact answer to your problem.