Abstract: CP-nets (Conditional Preference networks) are a kind of simple and intuitively graphical tool for representing conditional preference,three fundamental research questions of which are representation,reasoning and learning.Diffe-rently from the research point from statistical learning theory,the binary-valued CP-nets learning issues were studied based on logic theory.Firstly,an intimate relationship between satisfiability of proposition logic formula and preference assertion is given,therefore,the learning problem on CP-nets is transformed into the proposition reasoning.In the se-cond place,the computational complexity for learning two kinds of specific CP-nets is given,the learning problem of most complicated acyclic CP-nets is NP-complete,whereas the learning problem of the simplest set-structured CP-nets is P.These interesting results establish the upper and lower bound of complexity for learning specific structured (e.g.,list-structured,bounded tree-width) CP-nets.

Key words: Binary-valued conditional preference networks, Bounded tree-width CP-nets, Reasoning and learning, Satisfiability of propositional formula, Upper and lower bound of complexity