Is there anything known about the average case hardness of #SAT? Let’s say over a uniform distribution.
We know that in the worst case, it is #P-complete, but what can we say about an average instance of #SAT?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityIs there anything known about the average case hardness of #SAT? Let’s say over a uniform distribution.
We know that in the worst case, it is #P-complete, but what can we say about an average instance of #SAT?