Functions defined by evaluation programs involving smooth elementals and absolute values as well as the max- and min-operator are piecewise smooth. Using piecewise linearization we derived in [7] for this class of nonsmooth functions first and second order conditions for local optimality (MIN). They are necessary and sufficient, eespectively. These generalizations of the classical KKT and SSC theory assumed that the given representation of the function satisfies the Linear- Independence-Kink-Qualification (LIKQ). In this paper we relax LIKQ to the Mangasarin-Fromovitz- Kink-Qualification (MFKQ) and develop a constructive condition for a local convexity concept, i.e., the convexity of the local piecewise linearization on a neighborhood. As a consequence we show that this first order convexity (FOC) is always required by subdifferential regularity (REG) as defined in [20], and is even equivalent to it under MFKQ. Whereas it was observed in [7] that testing for MIN is polynomial under LIKQ, we show here that even under this strong kink qualification, testing for FOC and thus REG is co-NP complete. We conjecture that this is also true for testing MFKQ itself.