A possibilistic approach of planning under uncertainty has been developed recently. It applies to problems in which the initial state is partially known and the actions have graded nondeterministic effects, some being more possible (normal) than the others. The uncertainty on states and effects of actions is represented by possibility distributions. The paper first recalls the essence of possibilitic planning concerning the representational aspects and the plan generation algorithms used to search either plans that lead to a goal state with a certainty greater than a given threshold or optimally safe plans that have maximal certainty to succeed. The computational complexity of possibilistic planning is then studied, showing quite favorable results compared to probabilistic planning