3 ms·
> Counting solutions is #P-complete, though. Are you sure? Where was this proven? It could easily be that http://oeis.org/A000170 http://oeis.org/A000170 had a
by thomasahle 9y ago
> Counting solutions is #P-complete, though.
Are you sure? Where was this proven? It could easily be that http://oeis.org/A000170 http://oeis.org/A000170 had a polynomial time combinatorial formula.
Maybe some completion-counting problem could be shown to be #P-complete though.
- taeric 9y agoIf 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.
- thomasahle 9y agoComputational hardness doesn't depend on whether anybody knows an efficient algorithm. Just whether one exists.
- taeric 9y agoFair 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.