Abstract: Preference handling is one of the important researching contents in artificial intelligence, whose four studying hotspots are preference representation, preference elicitation, preference aggregation and preference inference. The conditional preference networks (CP-nets) is a simple and intuitive graphical tool for representing conditional ceteris paribus preference statements over the values of a set of variables. But there are very few works that address the problem of expressive power of CP-nets. In this paper, the expressive power of CP-nets is studied, in particular, preference completeness, some operations complexity of CP-nets and situation to which the model is applicable are discussed detailedly. Firstly, some operations of CP-nets are discussed; by using the improved Warshall algorithm, we solve the problem of worst case complexity of strong dominance testing with respect to binary-valued CP-nets, and prove its complexity is O(4n). Secondly, by constructing induced graph of CP-nets and studying its properties, we draw a conclusion that CP-nets suit multiple attributes qualitative decision making under incomplete preference information situation especially. When handling complete preference information, it can be fulfilled by interactive communication with agent. Strong dominance testing is a tractable problem in theory, but it is a intractable problem in practice. In order to solve this exponential order complexity, at last, some reduction techniques from qualitative judging to quantitative judging with soft constraint satisfaction problem (SCSP) are given. Because qualitative judging on c-simiring is of linear complexity, it increases the expressive power of some CP-nets. All these can be seen as the improvement and refinement of Boutilier and Bistarelli's related works.