カットの数え方とグラフが連結である確率の計算の複雑さ

いくつかの列挙および信頼性問題が# P完全であることが示され、したがって、NP完全問題と同じくらい難しいことがわかります。含まれているのは、ネットワークの信頼性分析における重要な問題、すなわち、グラフが連結である確率の計算および最小カーディナリティの（s, t）カットまたは指向ネットワークカットの数え方です。また、二部グラフにおける頂点カバーの数え方、部分順序における反鎖の数え方、グラフが連結である確率の近似および頂点のペアが連結である確率の近似も# P完全であることが示されています。