This paper considers the problem of decomposing a polyhedral surface or a polyhedron into simpler components: Monotone patches or terrain polyhedra. It is shown to be NP-complete to decide if a polyhedral surface can be decomposed into k monotone patches, by constructing a geometric model to make a reduction from SAT (satisfiability) problem. And the corresponding optimization problem is shown to be NP-hard. Then, the method is extended to the problems of decomposing a polyhedron with or without holes into the minimum number of terrain polyhedra, both of which are also shown to be NP-hard.