Summary: Possibilistic networks are graphical models particularly suitable for representing and reasoning with uncertain and incomplete information. According to the underlying interpretation of possibilistic scales, possibilistic networks are either quantitative (using product-based conditioning) or qualitative (using min-based conditioning). Among the multiple tasks, possibilitic models can be used for, classification is a very important one. In this paper, we address the problem of handling uncertain inputs in binary possibilistic-based classification. More precisely, we propose an efficient algorithm for revising possibility distributions encoded by a naive possibilistic network. This algorithm is suitable for binary classification with uncertain inputs since it allows classification in polynomial time using several efficient transformations of initial naive possibilistic networks.