5. To p or not p, that is the question

by anyarchitectanyarchitect on 1220357950|%e %B %Y
rating: 0, tags:

Ah… Shakespeare once again… this time with a lisp. But this is not really an analogy: The title of this article reflects the conundrum that many architects invariably finds themselves in but often does not verbalize sufficiently. Like Hamlet, one should be contemplating on the issue of "self-murder" but often we do not. At least Hamlet spent some time on "to be or not to be". Many of us simply go ahead and commit professional suicide The central question in this article is therefore: When a piece of architecture is being designed out there in the world, is it a real solution to a problem, or is it that the architect got just one solution and nobody can really be sure whether there could be another solution more apt than the one presented? Can one really know? Maybe mathematics could help unravel this issue further

Mathematicians differentiate between "p" problems and "np" problems. The "p" stands for "Polynomial" … which means things that can be solved within an polynomial time. "np" stands for non-deterministic polynomial which is a bit of jargon from mathematicians that is explained later on in this article Why should polynomials and mathematical esoterica matter to architects, one may ask. Well sometimes they intrude into one's life even if we don't know what they mean. So here are some definitions:

Polynomials: Mathematically, a polynomial is a mathematical expression involving a sum of powers in one or more variables multiplied by coefficients. A polynomial in one variable (i.e., a univariate polynomial) with constant coefficients is given by a(n)x^n + … a(2)x^2 + a(1)x + a(0).

Formulae: A mathematical expression becomes a formula when you bundle the whole expression together into a "shopping bag" and equate one to mean the other. Hence: ax + x^2 is only an expression. But ax +x^2 = y is a formula. One use of a mathematical formula is to act as representation of phenomena from the real world. The expression yields a value when you substitute the variables with real values and then calculate the value represented by the formula. For example, if you notice that an ant initially sitting at the position x0 on the x axis of the graph paper and it moved 14 cm horizontally in 1 minute, then you can predict where it could move to next by using the following formula: x = x0 + 14t Now you if you substitute 1 for t, then you would know that it would have moved 14 cms from x0. If you gave 2, then you would know it moved 28 cms and so on. (BTW, that formula is known as a parametric representation of a horizontal line)

In mathematics, a formula is a fact, rule, or principle that is expressed in terms of mathematical symbols. Examples of formulas include equations, equalities, identities, inequalities, and asymptotic expressions

Polynomial time So much for polynomials… now for "polynomial time" : When a formula is fed into a computing system (commonly known as a computer :-) ) then it would internally substitute the variables with values like the way we did by in the aforementioned equation of an ant travelling along a line and procure the answer. Some of these formula take a reasonable time to get an answer. That is because the individual parts of the polynomial do not influence the answer being calculated and so the mathematicians can expect the computer to solve it within "polynomial time". In the ant movement calculation; for example, the part of the polynomial concerning x0 did not influence other parts and we got the value for all values given for t ( Hey… what is architecture got to do with all this? Be patient… all in good time)

Now, mathematics is a great modeling tool. It has enormous symbolic capabilities, and believe it or not, mathematicians do look at the real world — albeit, symbolically. So when they are intensely scrutinizing a formula, dont be under the impression that they are spaced out and have got disconnected from reality. In fact, they would have taken a real world problem and given mathematical symbols to salient aspects of it and put them into one or more formulae. Now here is the issue: Sometimes the problem being modelled using mathematics don't fit neatly into a polynomial.

One example is where the parts of the expression themselves interact with each other — like so: If the ant was not moving on a straight line but was shot out of a cannon (!) then modeling the position of the ant using a straight line equation would not work. One would then need to factor in the acceleration due to gravity, and that from the canon, friction of air, wind speed, etc.

Mathematicians would have to put in symbols for each of those aspects, and also work out the connections between them. This means that just substituting "t" in one location of the formula like the way we did with the equation of a line would not give the answer but now the whole formula becomes one jiggly-wiggly thing where parts of it start interacting with each other during different moments of the poor ant's trajectory. The computer now takes more time to produce the results. Some of the modeling problems are so difficult, that computing them requires a special type of theoretical computer that is politely known as non-deterministic : i.e. many parallel computers working together as a system in order to solve the problem where each computer in the set cannot determine what others are upto.

Presumably, this is so that each of those computer in the parallel computer set, takes care of a limited set of factors in the equation with little interference (I need to verify this interpretation of mine though) . This is practically quite difficult This is why mathematicians put problems in a range of categories. Only at one end of the range are the problems solvable in a reasonable time. The range covers from "p" problems (whose solutions are found in reasonable time) to "np hard" problems all the way to "np complete" problems. The last are the hardest ones to solve because for those problems it would take an infinite amount of time for any computer to yield results.

There is this famous unsolved problem in mathematics where they are attempting to prove that if we indeed had a non-deterministic computer, it would be possible to get the solution in polynomial time whatever be the problem — p or np. In short in that situation P would be same as NP. But then nobody has been able to prove or disprove it There is another interesting way to look at P and NP problems. This is very well described in simple english in the web pages of the Clay Maths Institute which has installed a 1 million dollar prize for solving the aforementioned problem. (See reference below. It has an interesting example that practically describes the computing difficulty of NP problems without using maths jargon)

According to that article P problems are those whose solutions are easy to find and NP problems are those whose solution is enormously difficult to find but when found, the solution is easy to verify That is when we now talk about the process of realizing architecture (finally!): The process of design requires the use an internal representation system by the architect. Let us not get into the details of what that should be — let us put those details into a black box — let us say that there are many factors in that equation that needs to be considered. Now what we ought to do is to ask ourselves the Hamlet question; Do we have a p-problem that is being solved? Or is it an NP problem?

Many times, architects over-simplify a problem and the result is that what was essentially an NP problem is hammered into place and made to look like a P-problem. Some of us erroneously believe that the parameters being considered while designing do not interact one another and even if they do, we have the ability to work our way to understanding their repercussions. My personal position is that architectural design is essentially an np-hard problem. We ought not to jump directly to a solution, however appealing it may be and however intuitive the solution may look like.

At the same time, we cannot allow us to be so awe-struck by the non-solvability of an NP hard problem that no design comes out. Neither do I advocate that we throw reason to wind and apply some mystical philosophies and try to get away with whimsy. We need not dispair: There are famous examples in mathematicians of NP-hard problem which found reasonable (albeit slightly approximate) solutions in polynomial time. One such example is the "traveling salesman problem" (TSP) which was initially thought to be unsolvable. The TSP can easily be a part of a planning problem that an urban planner may face while designing towns. Come to think of it, it could be part of a simple architects problem without his knowledge — as it could have repercussions in the circulation space within the building being designed The statement of the problem is: "Given a number of cities and the costs of traveling from any city to any other city, what is the cheapest round-trip route that visits each city only once and then returns to the starting city?"

Translated into architecture: How should the circulation space in a building be designed so that a delivery boy who is delivering post to various offices in the building takes the least amount of time and ideally never revisiting the door of an office he had visited earlier? There are some very interesting solutions to the TSP that reach quite an optimal performance (Remember, solutions to NP problems CAN be verified) simply by representing the problem using genetics, fractals, etc. Wikipedia describes some approaches that one can take when dealing with NP-complete problems. Some of them are known to us architects (applying heuristics for example) but we may not have verbalized it in the jargon of mathematics. If architects do not sit along-side mathematicians (if they cannot learn the maths themselves) then the only real time tested way to solve the NP problems in architecture is just to gain experience. It is no wonder that most of the great architecture that the world has seen is attributed to architects who are at least sixty years old One attempt to reduce the complexity of np problems in architecture is to reduce artificially introduced complexity by ensuring that the problem is represented as accurately in the first place. Believe it or not, there are architects who are working on this; and that could be a story waiting to be told somewhere

References

  1. Polynomials
  2. Formula
  3. P vs NP explained simply
  4. Hamiltonian Circuit, a famous np-complete problem which can be described graphically
  5. The Traveling Salesman problem, a famous np-hard problem that has found reasonable solutions
  6. TSP solved, again a nice approximation, using a genetic algorithm
  7. Approaches to NP Complete

Back to mathematics


Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License