I have been intrigued by results of Shelah's classification theory. My interpretation of the situation is as follows ( it is full of simplifications, nonstandard terminology, and likely technical error; I welcome correction or a similar and more accurate interpretation): Given a complete theory T in a countable language L (so any L-sentence $\phi$ or its negation belong to T), we want to determine $\kappa=I(T,\lambda)$, the cardinality of the set of isomorphism types of L-structures which have an underlying set of size $\lambda$ and are models of the theory T. What properties of T can determine the value of $\kappa$?

Shelah finds that for many cases, the number of models is the maximum possible ($2^\lambda$) and that there are not many possibilities otherwise. He gives conditions for theories such as stable, superstable, and others which will (with other conditions) imply that there are fewer models (in fact, not many possibilities for $I(T, \lambda)$ as a function of $\lambda$). One of the conditions is (similar to the idea) that a well order is definable within the theory, and there are other conditions regarding definability within the theory.

When one is able to define such concepts within the theory, one can find more structure and determine limitations for the kinds of and number of models. I have always thought that greedy algorithms and other polynomial time solutions to certain problems were like these theories in which some structure was definable and that allowed for quick solutions (few models), and that other problems that did not have quick solutions could not because there was insufficient structure in the problem to find such a solution (too many models/possibilities to check).

When I have finished some other projects, I may return to this and draw a tighter analogy.

Gerhard "Wants Quick Solutions To Projects" Paseman, 2014.03.13