News for hackers. Stuff that matters.

A comment on The N-Queens completion problem is NP-hard. Parent comment

Re:The N-Queens completion problem is NP-hard by thomasahle on Monday September 04, 2017 @04:46PM (#15170762)
> 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.

[ Parent | on HN ]
Re:The N-Queens completion problem is NP-hard by taeric on Monday September 04, 2017 @05:11PM (#15170879)
If you read the cites on that link, you'll see that the value for 26 was only added in 2016. They do not have a closed form formula, or they would have shown it.

I mean, they could just be slow revealing. I doubt it, though.

[ Parent | on HN ]
Re:The N-Queens completion problem is NP-hard by thomasahle on Wednesday September 06, 2017 @08:22AM (#15183024)
Computational hardness doesn't depend on whether anybody knows an efficient algorithm. Just whether one exists.
[ Parent | on HN ]
Re:The N-Queens completion problem is NP-hard by taeric on Wednesday September 06, 2017 @10:12AM (#15183802)
Fair enough. I was obviously reading the above as having a polynomial time as having an efficient time one. Where efficient was shorthand for "quick." Both leaps, I concede were misguided.
[ Parent | on HN ]