The name "O(n2) Space" is chosen to focus attention on source of problem before proposing solution. The big-O notation is widely used as measure of software complexity in terms of required computing resources (memory and cycles). At the most basic level - writing software always involves reduction of quadratic complexity as close to linear as possible. However, the problem of reducing algorithmic complexity is only an example of more general "O(n2) problem".
General "O(n2) problem" is simple to explain using search engine software as an example: if each page on the Web needs to be related to another page in order to discover possible relevance (however small it may be), then it will require calculating n*(n-1) relations, where n is total number of pages. The simple (but not perfect) solution is an index, representing each page by set of keys so that all other pages represented by the same key are automatically related. Since the number of keys is much smaller than the number of pages - the problem is reduce to kn, where k is proportional to the number of keys.
However, the "O(n2) problem" would not go away easily: set of keys in the example of Web search needs to be constantly updated as pages change, and the number of keys can not be large. Therefore, the entire content of the Web would have to be approximated by a limited number of keys. And even though there are many better ways to approximate the Web content (such as ranking pages and employing sophisticated heuristics to improve precision of search algorithms), - it is simply not enough to keep up with changing content.
Another good example of "O(n2) problem" in software development comes from distributed computing - when multiplicity of different software agents has to communicate with each other over network. In this case every message has to be translated between each pair of agents, with n*(n-1)translations required to keep all agents "on the same page". There is also a good solution if the number of agents kept fixed or limited -"Hub and Spoke" toplogy. And again the problem would not go away easily.
Finally, there is a problem of maintaining "truth" - as required,for example, to support multiple commitments between parties in all unforeseeable events. Each new event could have implications that would require re-evaluating each commitment with respect to the event and all other commitments, taking O(n2) revisions in case of n commitments. It may be argued that the only thing in common between the examples above - is merely a mathematical expression, and that there is no such thing as "O(n2) problem" - instead there are many separate problems. There is, however, one common approach to solving these problems. It is based on understanding of combinatorial "explosion" as a phenomenon that is characterized by its large spatial extension, much like explosion in a physical space. The extension of logical statement consists of all situations that it covers. Software application hides that enormous set of possibilities behind a small set of "use cases". "O(n2) problem" arises when point of view is shifted. It can be avoided if the extension is projected using spatial transformation that includes the point of view or in logical terms - the "intention".
In software development two common ways to cope with "O(n2) problem" are: to limit user's choses and to make application more configurable. Doing so allows developer to avoid complete enumeration of all possible situations beforehand. Instead there is an implied "contract" that in most cases simply limits the damage. The alternative seems difficult - the software must be "smart" enough to self-correct, which requires it to "know" what was originally intended. In other words: extension (enumeration of behavior) must be substituted by intention (definition of goal).
This is where "O(n2) Space" approach provides a middle ground between mainstream software development and AI algorithms. Instead of analyzing behaviour of application in its entirety - it keeps extension in check at every step of application constructions by allowing developer to define intention of corresponding step in executing software. Obviously this approach would not work for every kind of software, but for database applications it works by propagating intentional information already present in database schema. A prototype tool developed at Next Generation Software, "OntoBase" demonstrates that it is indeed possible to apply the same set of constraints to data and logic built on top of it.