31–40 of 57 posts
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.
you're all idiots.
Earlier quoted context omitted.
Damn it. I didn't know it's NP hard. I thought I would discover the generating function for the number of possible solutions for board sized N.
Counting solutions is not a decision problem, so it can't be in NP. The corresponding counting complexity class is #P.
A not too silly example is counting partitions: the number of ways of writing a positive integer as a sum of non-decreasing positive integers (like 5=3+2 or 5=4+1 or 5=2+2+1). There's a dynamic programming solution with running time within O(n^3), so it is definitely in NP.
In another comment you mention that finding a solution to n-queens is not NP because it's not a decision problem. I'm confused because I thought the solution would be the polynomial certificate to the problem "an nxn board can be filled with n mutually non-threatened queens."
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?
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.
Earlier quoted context omitted.
Counting solutions is not a decision problem, so it can't be in NP. The corresponding counting complexity class is #P.
Do you mean that it's #P and not a priori NP? Counting problems can sometimes be in NP by deciding whether the count is the correct one (with the right encoding, function problems can be thought of as a subset of decision problems). A not too silly example is counting partitions: the number of ways of writing a positive integer as a sum of non-decreasing positive integers (like 5=3+2 or 5=4+1 or 5=2+2+1). There's a d…
It's currently solved for up to N=27 Both 26 and 27 solutions came from supercomputers/FPGAs and took months of compute time. http://www.nqueens.de/sub/WorldRecord.en.html
Earlier quoted context omitted.
Do you mean that it's #P and not a priori NP? Counting problems can sometimes be in NP by deciding whether the count is the correct one (with the right encoding, function problems can be thought of as a subset of decision problems). A not too silly example is counting partitions: the number of ways of writing a positive integer as a sum of non-decreasing positive integers (like 5=3+2 or 5=4+1 or 5=2+2+1). There's a d…
Finding a polynomial algorithm for #P problem implies P=NP.
Earlier quoted context omitted.
Counting solutions is not a decision problem, so it can't be in NP. The corresponding counting complexity class is #P.
Do you mean that it's #P and not a priori NP? Counting problems can sometimes be in NP by deciding whether the count is the correct one (with the right encoding, function problems can be thought of as a subset of decision problems). A not too silly example is counting partitions: the number of ways of writing a positive integer as a sum of non-decreasing positive integers (like 5=3+2 or 5=4+1 or 5=2+2+1). There's a d…
Essentially, #P is the class of problems where you compute the number of accepting runs for some problem in NP, so yes, #P and NP are closely related. You can turn a counting problem into a decision problem by a suitable encoding, but that turns it into a different problem (and the complexity depends on the encoding). The more natural fit for a class of decision problems corresponding to #P would be PP, the class of problems where the majority of runs on a probabilistic TM accepts, which contains NP.
> In another comment you mention that finding a solution to n-queens is not NP because it's not a decision problem. I'm confused because I thought the solution would be the polynomial certificate to the problem "an nxn board can be filled with n mutually non-threatened queens."
The point is that deciding whether there is a solution is not NP-hard (it is in NP though, precisely by your argument that a solution is the polynomial certificate that can be verified in polynomial time). Indeed, existence of a solution can be decided in constant time (and is thus in P), since there are solutions whenever n is neither 2 nor 3. Furthermore, for any given n (except 2 and 3), a solution can be constructed explicitly in linear time (for a unary encoding of n). Nevertheless, counting solutions is hard.
Earlier quoted context omitted.
Actually the queens problem starting with an empty board is not NP-Hard. See: https://cstheory.stackexchange.com/questions/12682/is-the-n-... The "completion" problem is the NP-Hard one. As one of the other comments noted, the paper behind this press release is about the completion problem.
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…
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.
Earlier quoted context omitted.
Do you mean that it's #P and not a priori NP? Counting problems can sometimes be in NP by deciding whether the count is the correct one (with the right encoding, function problems can be thought of as a subset of decision problems). A not too silly example is counting partitions: the number of ways of writing a positive integer as a sum of non-decreasing positive integers (like 5=3+2 or 5=4+1 or 5=2+2+1). There's a d…
> Do you mean that it's #P and not a priori NP? Counting problems can sometimes be in NP by deciding whether the count is the correct one (with the right encoding, function problems can be thought of as a subset of decision problems). It is unlikely that a #P-complete problem Essentially, #P is the class of problems where you compute the number of accepting runs for some problem in NP, so yes, #P and NP are closely r…
> Counting solutions is not a decision problem, so it can't be in NP.
Is this just a statement that it is a category error to compare the set of function problems with the set of decision problems? Sure, that's true, but you can still ask questions like "does this #P problem have a polynomial reduction to an NP problem."
> Nevertheless, counting solutions is hard
Do you have a citation for counting n-queens solutions (not completions like in the featured paper) being #P-hard? (or NP-hard?)