Let A be a nonnegative matrix, that is, a matrix with nonnegative real entries. A nonnegative factorization of size k is a representation of A as a sum of k nonnegative rank-one matrices. The space of all such factorizations is a bounded semialgebraic set, and we prove that spaces arising in this way are universal. More presicely, we show that every bounded semialgebraic set U is rationally equivalent to the set of nonnegative size-k factorizations of some matrix A up to a permutation of matrices in the factorization. Our construction is effective, and we can compute a pair (A, k) in polynomial time from a given description of U as a system of polynomial inequalities with coefficients in Q. This result gives a complete description of the algorithmic complexity of several important problems, including the nonnegative matrix factorization, completely positive rank, nested polytope problem, and it also leads to a complete resolution of the problem of Cohen and Rothblum on nonnegative factorizations over different ordered fields.