Proof search and Co-NP completeness for many-valued logics

We provide a methodology to introduce proof search oriented calculi for a large class of many-valued logics, and a sufficient condition for their Co-NP completeness. Our results apply to many well known logics including Gödel, Łukasiewicz and Product Logic, as well as Hájek's Basic Fuzzy Logic.