2006-03-26

The complexities of queries

I had this thought while buying strawberries at the local supermarket. Don't ask me why. Wait -- actually that's somewhat relevant. Inspired by computability theories, I was pondering if I could separate the five W's and an H into complexity classes. While carrying the groceries home, I gave it some analysis. Let me proffer my findings.

Let's start with the "easiest" queries. 'Where' and 'when' seem to be the simplest class of questions. In effect, the two are the same thanks to modern physics' space-time. Given that the answer is known, all that is required to relay the info is a vector v=(x, y, z, time), provided with a reference point in space-time. Let's call this class of queries Q1.

Next is 'who' and 'what'. It's obvious that 'who' is just an application of 'what' to human beings. To see why these are of higher complexity than 'where' and 'when', imagine relaying the answer to the querier when you've found it. You would need to describe it. The object o you are describing has characteristics; you could describe them by c = c1, c2, c3, ... etc. This may seem to be of the same complexity as Q1, the only difference that v is of variable length. Yet c may conceivably be infinite or undefined. For example, the answer to the question "what is the meaning of x?" The answer may furthermore depend on the entity which posed the question. This delves into the area of philosophy regarding the nature of truth: is it absolute, subjective, or something else? This I'm afraid is beyond the scope of this post. Let's call this class Q2.

Separating the last two types of queries is hard. Is 'how' simpler than 'why?' I believe so. 'How' (excepting cases like "how come", which is a colloquial way of asking 'why') requests a list or sequence of events that effect an outcome. One could then see this as an extension of Q2: each component in c, the descriptor, would be answers to Q2 or Q1 queries. For example, c1 would contain the first 'event' that triggers the outcome referred to by the 'how' query. This c1 itself is an descriptor to the Q2 query "what is the first event?" In this sense 'how' could be seen as an extension of Q2. Let's call it Q2x.

The remaining query is 'why.' Intuitively one can appreciate the difficulty of 'why' by comparing two oracles, one which can answer any of the above classes of queries, and one which answers 'why'. Which do you think is more intelligent? This shows that we humans in a sense respect the question 'why'. I believe that 'why' has supernatural connotations associated with it. An entity that could give 'why' answers in general would be viewed as a god. 'Why' also gives rise to questions for which even the existence of an answer is undeterminable. This contrasts with Q1 for example, since even if we don't know the answer to "where is x", we know that an answer exists.

What's ironic is that although past classes were each supersets of its prior class, the supernaturally difficult 'why' is not a superclass of Q2x but is simply unrelated. An oracle that answers 'why' cannot provide answers to even Q1 queries. "Why is the location of x?" No good, regardless of how it's phrased. 'Why' is in a superclass of its own; let's designate it W.

I posit a very coarse analogy of 'why' to the unsolvable problems in real complexity theory. The "hard but solvable" problems like the NP-complete ones could be Q2x or Q2.

So in essence, I find W ('why') to be in a realm of its own, and the class relationship Q2x ('how') > Q2 ('what', 'who') > Q1 ('where', 'when'). So... why did I chance upon this thought while buying strawberries? Too hard to answer, sorry. =P

5 comments:

Anonymous said...

Though I would argue against many of the simplifying assumptions you've made, doing so would TOTALLY miss the point of your fascinating bit of thinking, here! I especially like how you suggest that "why" is of a class of its own..; certainly, even to the layperson, "why" *does* seem more "transcendant" than the other questions, doesn't it?

Good work! ^^
-- Silph

Theomnifish said...

Oooh...the amazing tangents that the human can travel on while doing completely mundane activities is pretty neat, actually.

Unknown said...

I think in many cases, the best answer to "why?" is "why not?"

Theomnifish said...

Hey, I used to say that all the time! :P

Jason Yu said...

Heh, such a poignant reply ;P