4 ms·

I don't know why you're being downvoted. When Computer Scientists talk about "fast" they generally mean that an algorithm is solvable in `n^k` steps, with `n`

by dtech 9y ago

I don't know why you're being downvoted. 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.

ritinkar 9y ago
Isn't 2^n an exponential algorithm. I thought NP algos are still n^k but non-deterministic.
- umanwizard 9y ago
  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.
- johncolanduoni 9y ago
  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).
- pdpi 9y ago
  Both. As I understand it, polynomial time in a non-deterministic machine can be simulated as exponential time in a deterministic machine

by dtech 9y ago

ritinkar 9y ago

Isn't 2^n an exponential algorithm. I thought NP algos are still n^k but non-deterministic.

umanwizard 9y ago
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.
johncolanduoni 9y ago
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).
pdpi 9y ago
Both. As I understand it, polynomial time in a non-deterministic machine can be simulated as exponential time in a deterministic machine