Markov chains and phase transitions for TotP-complete problems.

We consider weighted versions of TotP-complete problems. We study the complexity of computing these weighted sums and show the existence of phase transition from NP-hard to approximate to approximable with FPRAS. We also study Markov chains for these problems and show the existence of phase transitions from exponential to polynomial mixing time.