 Subscribe!
My latest posts can be found here: Previous blog posts:
Additionally, some earlier writings: |
The Initial Ideas ...A short time ago I was chatting about and working on some puzzles with a friend, and casually mentioned something about how the time complexity of this particular problem behaved. What then transpired was that my friend didn't know anything about how the whole "Time Complexity" thing worked, and didn't understand about $\mathcal{P}$ versus $\mathcal{NP}$ and similar concepts. For normal people that wouldn't perhaps be so surprising, but this friend is an outstandingly good mathematician, so I was caught out somewhat. But two or three years ago I'd been writing an article, or post, or book, or something, and never got round to "publishing" it in any form. So here it is, in, what I hope, will be bite-sized, accessible chunks. I would really appreciate feedback on this. Although I'm posting it as a series of pages on my bloggy thing, I intend to come back and refine them as people point out errors, or places where the explanation could be improved. I'd love that - doing so would, to some extent, have the effect of "crowd sourcing" the posts/pages to become a decent resource. And so we begin ... What is "A Problem?"There are many connected concepts, and in discussing these ideas with people I've found that many of them have the basic ideas, but not the technical understanding. And that's perfectly reasonable, because most "popular writing" doesn't actually give the technical definitions. And to some extent I'll be walking a rather fine line here as well, since I don't have the background to go into the deep technical details, but I'll try to be interesting and informative. I'm going to talk about X different problems as specific examples, where X may well change. To start with, here are the "problems" (yes, that will become a technical term) I'll be using:
Some of these may not be familiar to you, so we'll start with one that shouldn't take too much explaining: SQR. So here's the setup. I have a set of 3x5 cards, and on one side is an integer. That's the side that you'll get shown, and on the other side is the square of that integer. So I might choose a card and hold it up to you, revealing the number "23". Your job, the problem you face, is then to tell me what's on the other side.
But the idea is that one can "compute" what's on the other side. So one "instance" of the problem SQR is the number "23". So here's a summary of the important terms (and don't worry, we'll go over these again):
Looking forward ...I've started with SQR because it's easy to describe, and it feels fairly familiar and straight-forward, whereas some of the other problems are unfamiliar, obviously complicated, and it will come as no surprise that there are some tricky questions about them. What may surprise you is that we are already on the verge of some research level maths into unanswered questions.
Send us a comment ...
|
Suggest a change ( <--
What does this mean?) /
Send me email
