Ov3rload

Why would you ever use a regex to do this, apart from experimenting?

This would be much easier to do with a context free grammar or any decent parsing library.

There are many proofs, you can find some of them here:

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Like all famous problems, P vs NP attracts a great number of people, mostly amateurs, that want to try to solve it. Most of those proofs are not peer reviewed, all of them are probably wrong.