Phenomena from a variety of disciplines, including biology, computer science and sociology, can be modeled by graph dynamics in which nodes are associated with states and the node-state association changes in time. Although general k-state dynamics have been considered, most of the research in this area refers to binary dynamics especially as far as deterministic dynamics are regarded. In this paper 3-state deterministic dynamics are studied from the computational complexity perspective. A tractability result is proved when the third state is a state of neutrality, adopted by any node unable to establish a preference between the two remaining states. Subsequently, two hardness results are proved for two cases where each of the three states represents a semantically distinct state: the case in which a state change occurs in a node only if the most preferred state among the remaining two receives a suitable number of preferences, and the case in which a state change occurs in a node only if its current state lacks sufficient preferences and the most preferred state among the remaining two receives a suitable number of preferences. Finally, the relation of the last two results and a conjecture from the 1980s is discussed and it is shown that the conjecture is contradicted in both cases.