In “Commentationes Geometricae” Euler asked when a sets of points in the plane is the intersection of two curves, that is, using the modern terminology, when a set of points in the plane is a complete intersection. In the same period, Cramer asked similar questions so that this type of questions is presently known as the Cramer-Euler problem. In this paper, we consider a generalization of the Cramer-Euler problem: characterize the possible complete intersections lying on a Veronese surface, and more generally on a Veronese variety. The main result describes all possible reduced complete intersections on Veronese surfaces. We formulate a conjecture for the general case of complete intersection subvarieties of any dimension and we prove it in the case of the quadratic Veronese threefold. Our main tool is an effective characterization of all possible Hilbert functions of reduced subvarieties of Veronese surfaces.