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.

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

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

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.

Both. As I understand it, polynomial time in a non-deterministic machine can be simulated as exponential time in a deterministic machine

The time it takes to solve needs to grow at most polynomially with the length of the representation of the input.

The input is just a single number. So grow polynomial from N x N board size?

I really don't get how this is equivalent to NP.

You either read the earlier version before it was corrected, or you're misunderstanding. The problem is not the N-Queens problem, it's the N-Queens /completion/ problem. The problem is this:

Here's an NxN board with k queens already placed. Is there a way to place another N-k queens so they are all mutually non-attacking?

Most instances will be easy, but current algorithms to solve this are such that for each N, the time taken in the worst case is an exponential function of N.

Ahh, thanks it looks like it was changed after I read it.

If you can solve it at all for even 50x50 would mean a revolution in certain algorithmic fields.

That is surprising.

Can you point me to a concrete reference about the 50x50 number?

Modern SAT solvers should be able to handle that, maybe with a few problem specific tweaks.

That's a bit too simply put, unfortunately. You could do that with an `e^{n/50}` solution. That wouldn't really be unexpected.

You have to be P=NP fast. ;)