The Idea is this:

The Decision problems Max Cut for graphs is APX-Hard and therefore does not have a PTAS.

However Dense versions of Max Cut do have a PTAS!

This suggest that Counting Perfect Matchings for Dense Bipartite Graphs could have some sort of speed up.

Does such a speedup exists in the complexity literature?

Further to the above, I am aware of the expectional work done on NonNegative Matrices. However I was really thinking about General matrices and expecting exponential algorithms. Of course #P is by standard complexity theory intractable!


What about



If you are looking for exact algorithms, the only speedup I'm aware of is


Which also can be used to show you can do c^n time for c<2 for sparse 0/1 matrices or the UP-hard mod 3 permanent.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.