Complexity of listing all minimal cut sets / connected 2-partitions of a graph
dear all. There is no contradiction here. The problem of listing or enumerating all cutsets is a counting problem which is #P-hard. The class #P consists of all the problems that can be solved by a non-deterministic counting Turing machine in polynomial time. Therefore, the class #P is useful for classifying counting problems. On the other hand, the class NP is suitable for classifying  decision problems. A decision version of your problem would be, for instance: Is there a cutset with cardinality less than $k$? Obviously, if you can enumerate all the cutsets in polynomial time, then you can also say in polynomial time if there exists a cutset with cardinality less than $k$. In other words, the counting version is at least as hard as the decision version.  Therefore, if a counting problem is #P-hard, then it is NP-hard (I am talking about the same counting problem, not its decision version). However, the converse is an open question. In other words, for the time being, saying that this problem is #P-hard is a stronger statement than saying that it is NP-hard.