Hacker News
points by danbruc 2 days ago | 0 comments
And the claimed algorithm solves the counting problem, i.e. determining the number of different solutions, which in many cases is much harder than just determining whether a solution exists or finding one of the solutions.
[–] a115ltd 2 days ago
Knowing the count also gives you a O(n) way of finding a solution.
[–] dragontamer 2 days ago
No.

The number of valid permutations of 10 things is 10!. Reviewing all 10! Things is clearly exponential or even worse than exponential.

We can get the count of 10! pretty easily, far easier than trying all combinations manually.

[–] danbruc 2 days ago
The parent comment is correct, if you can count the solutions, it is easy to find a solution. Assuming there is a solution, you set the first variable to either true or false and then count the solutions. If it is zero, you made the wrong choice and the first variable must be set to the opposite value. Repeat for the remaining variables until you have fixed all of them and found a solution. This takes n invocations of the counting algorithm and is probably what the parent comment means with O(n) even though this is not correct as it is O(n times whatever the counting algorithm runtime is) and not just O(n).

But the parent comment also missed my point. They have an algorithm for the counting problem which also provides a subexponential algorithm for the decision and search problem. But they could have refuted the exponential time hypothesis with a subexponential search or decisions algorithm which would not [easily] provide a subexponential counting algorithm.