41–50 of 57 posts
What you is fast in this case? If you can solve 1,000 x 1,000 in say 1 minute is that fast? Or do you need to solve 1,000,000 x 1,000,000 in a second?
If you can solve it at all for even 50x50 would mean a revolution in certain algorithmic fields.
Earlier quoted context omitted.
That's just a good heuristic, though, it does not guarantee finding a solution. Also note that NP is a class of decision problems, and finding a solution for the n-Queens problem is not. None of the two decision problems that arise naturally from n-queens, deciding whether there exists solutions for a given board size, and verifying whether a candidate is indeed a solution, are NP-hard (solutions exist for n \not\in…
> Counting solutions is #P-complete, though. Are you sure? Where was this proven? It could easily be that http://oeis.org/A000170 had a polynomial time combinatorial formula. Maybe some completion-counting problem could be shown to be #P-complete though.
I mean, they could just be slow revealing. I doubt it, though.
Earlier quoted context omitted.
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.
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.
What you is fast in this case? If you can solve 1,000 x 1,000 in say 1 minute is that fast? Or do you need to solve 1,000,000 x 1,000,000 in a second?
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…
Earlier quoted context omitted.
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…
Isn't 2^n an exponential algorithm. I thought NP algos are still n^k but non-deterministic.
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.
I find it more likely that the N-Queens problem will have a very specific solution
Earlier quoted context omitted.
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…
The article completely misinterprets the press release[1]. The University of St Andrews isn't offering a prize; they've just shown that the Queens puzzle on an n-by-n board (EDIT: actually, the n Queens completion puzzle) is NP-hard. (By the way, even the press release, though less wrong than the article, is still pretty bad: apparently NP-complete problems are hard because they use "backtracking". Also it seems to s…
If I'm reading it right, they haven't shown that the N Queens problem is NP-hard, but rather that the N Queens completion problem is NP-hard.
oh well, there goes another account.
Earlier quoted context omitted.
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…
Isn't 2^n an exponential algorithm. I thought NP algos are still n^k but non-deterministic.