One of the most basic notions in polynomial system solving is feasibility: does your system of equations have any roots? We will explore the algorithmic complexity of this problem, focussing on sparse polynomial systems over the real numbers and complex numbers. Over the complex numbers, we will see algorithms completely different from homotopy, resultants, and Grobner bases; and how the Generalized Riemann Hypothesis enters our setting. In particular, we show how earlier methods (of Grigoriev, Karpinski, Odlyzko, and Koiran), depending on unproven number-theoretic hypotheses, can be made unconditional in certain cases. Over the real numbers, we will determine the threshold between polynomial-time and NP-hardness, as a function of the number of variables and monomial terms. In particular, we will give polynomial-time algorithms where only exponential-time algorithms were known before, and we will see how Diophantine approximation enters in an unexpected way. Along the way, we will see how finite fields and p-adic fields are also related to our main focus.