Monday, February 28, 2005

Welcome !

Today's post:

Quantum Turing Machines and N/P
Group Theory and Math teachers
A Hacker Update

I read an interesting paper on quantum mechanics from the Bulletin of Symbolic Logic last night, (but whenever I read about the subject, I have salt grains handy: although the authors obviously knew what they were talking about, and even though a few sections of text were out of order, the ramifications of their discussion and the research it presents just seems too encompassing and too leading: I wanted to scream out, "SAY IT ! SAY YOU THINK P=NP ! IF THIS IS TRUE, DOESN'T IT MEAN NON-DETERMINISTIC TURING MACHINES CAN BE CREATED DETERMINISTICALLY?! DOESN'T THIS MEAN NP COLLAPSES TO P?! ALL NP PROBLEMS COULD THEN BE REGARDED WITH NEW ALGORITHMS TO ACT IN THIS FASHION AND SOLVE IN POLYNOMIAL TIME ! It doesn't make sense ! If I were to reference that paper alone, or EVEN the most quoted generalization to arise from Quantum Mechanics (an object can occupy two spaces at the same time) I could make the claim of a new Turing Recognizable machine that allows itself to take multiple paths down a decision fork, and still call such an action ONE transition! The equivalent standard Turing Machine has the choice of handling one path at a time, or handling each path step concurrently, but this "Quantum" machine would be capable of handling more than one at a time! Wouldn't that allow O(n^n) complexity to become O(n) if one takes steps to ensure that the computational load is balanced when an algorithm branches? After all, the number of paths the algorithm must take would simply become ONE for a Quantum Turing Machine... And I can certainly think of many NP-Complete problems that would become P, much less ONE, which is all that's needed to prove P=NP.
BUT... Something's wrong. That paper was simply a well-researched study on information already well-known... published in November of 2000, (Well, it was also written by the individuals who actually introduced the idea of quantum turing machinges.) By all accounts, even someone just one year into their math major should be able to prove P=NP with that much to go on. Certainly, Quantum Computing has been proven to be a very attainable reality. What's missing? Why aren't we basking in the glory of powerful computing? Except for the fact that the new technology is going to take a while, and the question of whether the underlying system that controls the physics of our universe really represents the same non-deterministic model that our universe does, I don't know. I wish I could say for sure about the proof, but there's something more than just continually refining our methods of analysis. I will read more on it, and hopefully find out why no one with dedicated interest on the subject has yet proven it, with or without a Quantum Turing Machine Variant.

--- UPDATE: My fears are confirmed: Apparently, there are many papers written about the subject, and even about running non-polynomial time algorithms in polynomial time, but no actual "proof" per se ! It's bizarre ! By all accounts, shouldn't the people who introduced the concept and the people who proved it possible be given an award? shouldn't we consider P=NP ? Shouldn't we be researching the ramifications and applications now ?! What the hell is going on ?!
To give you an idea, here is one of MANY papers discussing the matter in detail... fortunately, this one gives a slightly better insight into why there isn't 'exactly' a proof yet: Here
Just search for Quantum Turing Machines and P and NP at your favorite search engine for more information.

I will be posting simplified and condensed facts, theorems, and observations in Group Theory and modular notations continually throughout the rest of this season.
Why ?
Algebraic Structures are not hard to understand!


Math teachers must spend less time PROVING concepts, and start teaching them! Every math class I've had, the teacher spent the majority of time on proving concepts before teaching or even explaining them ... which gave little time for teaching ... even in classes where the teacher gave examples and practice, more time was spent in proofs. Give in-class practices, examples, and reasonably-useful reminders for the students to work through.(read: for the STUDENTS to work through - not copy off the board) Proving is done in proofs and AFTER introducing the pre-requisite concepts ... prove it after your audience is familiar with its use. Yes, we students appreciate what you have to offer - but we think you have much more potential within you - at the very least, as much potential as you believe resides in us.

Hacker update: Mozilla's Firefox can be used not only as a wonderful browser and webmaster tool, but also to edit forms (locally! Not remotely!) on a page, even with a secure connection ... essentially, you can use Firefox tools to bypass client-side verification without disabling javascript.

Now I know what most of you are saying already: "You fool! I've been doing that by simply downloading the page to my hard drive and editing it there!"
That won't work when the server has a secure connection, when you need to log into an account to input your data, or when the server checks if your local copy's address matches its own.
But The DOM Inspector will.
In fact, it's not all that suprising. It'll only be a matter of time when the first browser comes along that allows you to completely, dynamically, and easily customize the page that gets sent to you concurrently while you're connected to its host server.

Thus, for those of you who think client-side verification is nifty, for those of you (for whom my dislike is strongest) who think you can discourage people from viewing your html source code by using annoying little tricks that simply annoy people who are just trying to view your website, for those of you who think you can password-protect or encrypt your pages using client-side javascript, stop hallucinating. If it was important to someone who knows what they're doing, they've already gotten what they needed from your site. There are many ways to access that data, and your safest bets are to stay away from form submittal (you can still use them for input retrieval, although there are now safer methods), use xmlhttp, and a nice compromise between client-side and server-side processing of data: don't let the client computer verify important info- instead let it take care of xml serialization and de-serialization, let it take care of everything possible that relates to the client's visit to the server except secure data, and required data that can be falsified - use a direct connection to the server to verify that stuff. This will all be covered in detail at with example sourcecode on how to secure submit forms and maintain heavy client-side processing as a best-case. (For best compatibility, one should always maintain the worst-case scenario: full server-side processing upon detection of an old browser)