The coming decade is going to see a push towards exascale computing. Assuming gigahertz cores, this means exascale systems will have between 100 million and 1 billion of them to achieve this level of performance. At this scale, some important questions need to be answered on the applications end. What applications are feasible at this scale? What needs to be done to make them scalable? How does the hardware have to adapt to meet application needs? In this paper, we introduce a new feasibility-based approach to answering these questions. Our approach involves finding upper and lower bounds on problem size and machine parameters to determine a feasibility region for the application in question. As the underlying architecture of a future exascale machine is currently unknown, we use LogP-based performance models and vary machine parameters to give architecture-indepenent hardware constraints. We consider both strong-scaling and weak- scaling scenarios, and present results for two applications, the Fast Fourier Transform and basic geometric multigrid. The results show substantial constraints that need to be satisfied to enable exascale performance.