Older blog entries for harrisj (starting at number 31)

Pseudonym: Thanks for your answer. You are a veritable font of knowledge on the subject. I'm quite impressed.

I'm a bit rusty from when I took a class on theoretical computer science a few years back. Can you perhaps briefly describe some of the more interesting properties of EXPTIME. I'm particularly interested in verification time vs. calculation time. For instance, I know that an NP-time problem can be verified in P-time (I think this has been proven). Is this also true of EXPTIME problems, or is verification in a higher class, or is it simply unprovable.

EXPTIME measures execution in time, EXPSPACE measures execution in space. It is known that EXPTIME is a subset of EXPSPACE, but not known whether it is proper containment or not (all we know is that P != EXPTIME, right?). This is correct. I'm still trying to get an idea of what the "meaning" of EXPTIME is. Mainly, what is an example EXPTIME algorithm?

schoen: Thanks for your interesting points. It reminds me of a debate I had with a coworker here at work. I found the whole idea of morality being impossible without fear of divine authority a bit absurd. But whatever. People can believe in whatever they want, but I can't stand it when they pass judgement on me as a result.

schoen, Pseudonym, and yakk: Thanks for your input. I knew that factoring was in NP (although nobody is able to prove that there is NOT an algorithm in P). I was under the mistaken impression that it might be NP-complete as well. So finding a P algorithm for factoring won't show that P=NP as I erroneously suggested.

I did know that quantum computers would do factoring in P. How do they work against other NP-complete problems (like Hamiltonians)? Also, is there a class of problems which quantum computers can not do in polynomial time (eg, how well do they do against EXPTIME)?

I have found that Sipser's "Introduction to the Theory of Computation" is a good primer for all of this, for those that are curious. Now to work on a provably EXPTIME-hard encryption method. I think I can bang one out this weekend. ;)

More notes on theoretical aspects of encryption might be found at the course notes for the MIT class 6.857 taught by Ron Rivest. It took it in 1996, and it was most informative. Perhaps it can answer mattbradshaw's question a bit more coherently than me.

Addendum

It seems that Public Key security is based on the difficulty of solving the Discrete Log Problem. For large prime numbers p, finding the factors for p-1 seems to be a difficult problem. No P-class algorithms are known, but it is not really easy to prove none exist. Searches for "Discrete Log Problem" might be useful for more information.

Was it Bill Gates who said that one of the challenges for future computer systems is "factoring large primes?" ;)

The sun was born/ so it shall die/ So only shadows comfort me...

Really tired here at work. Went to see VNV Nation and Apoptygma Berzerk in concert last night. A truly incredible (almost religious) experience. The venue (the Limelight) is a huge converted church, with a main performance floor and several outlying bars. The gothic ceilings, and original stained glass are impressive. There are also two stories of catwalk above the stage for better view of performances. I was thrilled that the concert was there, because it is one of the few times I get to go to the Limelight without dealing with hip hop and Bridge and Tunnel people.

Both bands put in solid performances. VNV Nation had an impressive backing video, and it amused me to see "DVD Play" appear on the screen behind them before they came on. Apoptygma Berzerk had an even larger screen with stage lights on it. It was amazing. I haven't danced so hard in quite a while, and I finally staggered home at 2:30 am (up at 8:30am). Thank goodness for coffee. I have to go to a seminar on XBRL this afternoon, so I'll probably need a refill so I don't fall asleep.

My sister sent me the Job doll from TrainUpAChild. Excellent. I've never owned an action figure with open sores before...

Addendum

mattbradshaw asks why the difficulty of factoring large numbers is essentially unprovable. Here's a quick summary. Theoretical computer science defines P algorithms as those that can be completed in polynomial time (eg, O(n), O(n^2), etc). A more difficult class is NP algorithms. These can't be solved in polynomial time (eg, O(2^n), O(n!)), but can be verified in polynomial time. In order to prove that factoring large numbers, you would have to prove the NO P-class algorithm exists for doing such an operation. Establishing existence in proofs is easy, but nonexistence is usually not possible. Although we haven't found a P solution yet, there is no good way to prove one doesn't exist. Of course, if you did find a P solution, I think you might also prove that P=NP, getting the acclaim of all theoretical computer scientists everywhere.

Another Addendum

squiggy: The problem stems from several limits. Search engines can be very big (500 million pages). Due to limitations on bandwidth and processing, most of them only have a monthly refresh cycle for their indexes. Unfortunately a lot can change in a month on the web. Another limitation is that you are only really allowed to request pages from a given web server once every 20-30s (if you want to be polite and not piss them off). This means you can only make some 2000-3000 requests against a given web site a day. This increases the time it takes to index a site, reducing its frequency in a given period.

Potentially, you could write some batchmode processes to verify that links in the index are live. However, this must still obey the 20-30s rule, and since you're checking pages, most search engines feel that you might as well just wait until the next reindexing cycle. There are some other potential solutions, but I can't really go into them now.

The XBRL symposium was boring. Too much explaining to CPAs why XML might by a Good Thing(tm) for financial reporting. Duh.

Listening to loud industrial (VNV Nation & Assemblage 23 right now) here at work. Seems rather appropriate for the moment for some reason. Mix in some odd German electronic music and you have a typical Jakemusic set for work. People used to cringe at the SIPB office whenever I headed for the stereo with a disc in my hand...

I think that many people are correct, in that technology is fun, but it's not a life in itself. I think too many in this industry work too long for no good reason. Perhaps a dream of future wealth that maybe comes through, but maybe results in making lots of money for other people and burning out by the age of 30. Perhaps a general fear of life outside of work, with all those things outside of your control. Perhaps just a sheer inertia or peer pressure. All I know is that you have to take control of your life, if you want it to turn out the way you want. You can't predict the future, and you can't avoid mistakes. But you can't just hope that things will get better, and wake up one day feeling it's too late.

Programming should be your job. It shouldn't be your life.

The masochistic pride in this life has always disgusted me. Nerds complain about being marginalized by society, but it's always struck me how much of this marginalization is self-inflicted. I was always depressed by students in school who were horrified they had to take humanities classes. Who couldn't talk about anything besides their narrow areas of interest, especially to people outside their small circles. Who would be on the computer constantly when they weren't sleeping. Who now are probably living the same life as 4 years ago, and will still be the same in 20.

Get out. Go to a museum. Read a real work of literature. Write music. Paint, sculpt, blow glass even. Walk around. Most important, talk to people. Broaden your horizons and connect. The machines can wait. Perhaps you could make a movement out of this. I think that might be what TechnoRealism was supposed to be, before it dissolved into vapor.

Sorry if I offended you. I'm just a ranting old coot anyway...

Was thinking about squiggy's diary entry. It's an unfortunately common problem in America. We work hard to get to a place, only to find out that we're not too happy with it, once we make it there. I think Squiggy has the right idea though. Rather than launch into a Midlife Crisis in an attempt to follow paths not taken (in essence, a frantic effort to relive your life differently), I think it's better to become more comfortable where you are. To be perfectly aware of the moment. To stop and look at the sky (or smell the roses), instead of thinking about other projects and racing to work.

It's a Zen thing. Nirvana is not a state of blissful isolation, but a harmony with the world around you. A dissolving of self into the universe, such that there are no dualisms, no distinctions, just existence in the moment. (Nerds can also think of it as a Yoda thing: "Always rushing off, never thinking of where he is, what he is doing!")

I'm not sure why this happens in America. I suppose it could be the promise of the American Dream. Maybe it's the Puritan Work Ethic, driving us to keep working and not relaxing. Of course, we're one of the few nations where people can actually contemplate our lives being different and make it happen. In the third world, if you're born a rice farmer, you die a rice farmer. Something may seem radically important to you, but 20 million Chinese don't give a damn. While we have more options, they can be overwhelming at time. As Devo said, "Freedom of choice is what you've got. Freedom from choice is what you want."

I went to the Barneys Warehouse Sale this weekend and got a new suit (normally $800, only $140). Black pinstripe. I've gotten more into dressing nicely for work lately. Even ties sometimes. I think it's largely a reaction to the normally predictable fashion sense of developers (jeans and a free T shirt from a trade show). Plus, good clothes can be comfortable and give you a certain confidence. It's true. The clothes do make the man.

In some ways, it's a lot like Rasterman wearing Victorian outfits while he was a Red Hat. I do try to look nice, and I do try to look different, but not in a way that makes me look like I'm from sales or other pointy-haired-boss material. More like a trendy Village hipster I suppose. Luckily, Manhattan can be a decent city to find good and distinctive clothes in. Sure, the thrift stores are mostly crap (because everybody goes there), and some of the vintage places suck, but you can also find huge clearances and such on downright new clothes. Century 21, warehouse sales, Daffys, etc. are great sources for nice clothes for really cheap.

Surprising but true. The last few evenings I have had ICMP monitoring software running on my machines at home checking to see if any script kiddies were scanning me. Not a single ping. No firewall, so unless the wireless base station is blocking pings, it seems that there aren't as many 3L33T HaXoR kids out there as the media seems to believe. (Yes, I too can write like Biff...)

Otherwise, it's Friday before Labor Day. The city is starting to empty out already. It can be downright eerie walking through New York early in the morning on summer holiday weekends. Still, it's great if you're going to brunch or any other activities, since the crowds are much more manageable.

Rasmus, you're correct about our similar setups. In my case, it's an Apple Airport basestation that is connected to the ADSL modem. This in turn talks to Farallon SkyLine PCMCIA 2mb cards in both a Powerbook G3 (running MacOS and LinuxPPC), and my SO's Windows95 laptop. I need to figure out how to get LinuxPPC to support the card, but I might just instead play with MacOSX Beta in 2 weeks instead. I don't have a firewall in place yet, so I should scan me some ports now to make sure everything is locked down security wise. :)

802.11 wireless networking is pretty cool. It's nice to not have to run wires.

Otherwise, nothing much new. I am a bit concerned about the GPL revision thread (aka "License to Kill"), but am not coherent enough to really post an argument. In brief, the problems I have:

1. I'm not sure it can be legally watertight (unless you want to pass UCITA I suppose).
2. It is meant to have a chilling effect of lawsuits and patent infrigement suits. While I agree that most of these are bad, it can also discourage potentially legitimate cases.
3. It can discourage the spread of free software, since its use would entail the surrender of certain rights and priveleges. How many businesses will agree to that?
4. Where do you draw the line on enforcement? Someone else has pointed out that the production houses are parts of studios, which are parts of the MPAA, and thus have no real input on the lawsuit. Should they be penalized?
5. Who actually evaluates transgressions of this license and launches the lawsuit?
6. It seems pretty small-minded.

Ah well. What do I know? Good principle, but it just seems as scary to me as UCITA.