Coding Horror: The Girl Who Proved P = NP | Hacker News Reader

Coding Horror: The Girl Who Proved P = NP

codinghorror.com

25 pointsAnon8423 comments

even with computers that operated at, say .. the speed of light.

As opposed to our modern day computers, driven by steam and turtles.

Haha reminds me of the quote from Richard Nixon's Head in Futurama: Listen here Missy, computers may be twice as fast as they were in 1973...

Funny, but electricity does not move as fast as the speed of light in a vacuum, just a fairly reasonable fraction.

Do you mean that electrons do not travel at the speed of light in a vacuum? I understand the word "electricity" to mean the macro-effect that makes it appear that electrons are moving through a substance (in reality, something else is happening, of course).

Right, actual, physical electrons move about as fast as sap in a conductor. I'm sure the OP meant the speed of electric charge, while still not moving at c, it is a decent fraction of it.

Two second explanation that I'm sure everyone knows: When you imagine a conductor to be a pipe full of electrons that are all annoyed at other electrons, once you pop another one in from one side, that annoyance (charge) percolates up to the other end and pushes an electron out from the other side. This is what people claim is actually moving at close to c, not the physical electrons. Electrons are matter and thus can't come close to c. This is why AC is a lot more efficient at transmitting electricity: with alternating current, you push and pull a couple of electrons from each side really fast, and the 'meat' of the charge isn't moving more than an infinitely small distance. When you have a current flow that never changes polarity, you're always pushing charge in the same direction.

What I find really interesting is the relationship between conducting 'electricity" and conducting heat. Why is the property of electrical conductivity closely correlated with the property of heat conductivity?

http://www.amazon.com/gp/product/0521456606?ie=UTF8&tag=...

I think the most general answer is density, but there are actually several indecent properties’ that change the rate of the propagation of both heat and electricity.

Copper becomes a better electrical conductor as it cools. However, hydrogen is a far better conductor as plasma than as a cooler gas. Yet heating things tends to increase their ability to conduct heat.

It's like sound: the air isn't moving that fast.

To paraphrase what others are saying, and to add a folksy image to picture what's happening ...

Electrons in a wire move like a snail on valium. The signal, on the other hand, move fast. It depends on lots of factors, but the figure I use is 8"/ns. It's wrong, but close enough for (most) Government work. For reference, light in air travels at about a foot per nanosecond.

So how does the signal travel faster than the electrons?

Image a long tube that's just big enough to have a ping-pong ball roll down its length. Now fill it with ping-pong balls. Have someone put their hand on the ball at one end, and tap the other end. The signal travels really, really fast, but the balls have travelled almost not at all.

The signal does take time to travel because the balls are compressible. In the case of electrons in a wire, the electrons can get closer together (or further apart), and that creates a push (or pull) force.

All that can be made more precise, but it's a good working model. Good enough to make calculations if you're careful enough, and remember that it's just a model.

And all models are wrong, but some models are useful.

Summary: Jeff quotes what several blogs (and XKCD) have said about P = NP. As such, he gets it mostly right, but doesn't add much to the discussion.

He did link to the really awesome blog entry from Accordion Guy... that has some marginal value... I guess.

Would've rather just had Accordion Guy's entry be on here.

s/much/anything/

Yeah, but he got it mostly right. That's a rare achievement in CodingHorror-land....

We often complain that certain link-baiting, populist posts are not worthy of HN's front page. The retort is usually along the lines that while the post is of little interest, the discussion around it may be valuable. I hope that we can reach that standard here. Just as the post adds little to anyone's understanding of tractability, flaming the post for that fact adds little to HN :-)

Right you are. Even though Jeff has never said anything that inclines one to think he actually understands what NP-completeness means, (I suspect he still thinks it's like porn) I must say his remark about computers operating at the speed of light did lead me to read the wikipedia article about optical computing, which is way more interesting. :)

http://en.wikipedia.org/wiki/Optical_computing

If you don't feel like proving that P=NP, a proof that there is no proof of P=NP within our current systems of mathematics would be insanely important.

Jeff Atwood should be prohibited from ever putting the letter "N" next to the letter "P".

Conveniently, the Internet allows us to enforce that rather easily: http://www.morewords.com/contains/np/

Just keep an eye out for an article on moonports or vanpools.

His last N posts pretty much add nothing to the conversation while making a few key sentences in bold.

There is a subtle Futurama joke about P=NP in one of their episodes (the size of the books on the shelf):

http://www.mathsci.appstate.edu/~sjg/futurama/futuramatalk10...

Any reason for "The Girl" in the title?

Yeah, some of us are late on this story. Considering a second HN post just above this one (The girl who cried webmaster) refers to the same story, and the original post on that blog was deleted, I have no backstory. Can someone fill us in?

That's impossible! We had a test where we had to prove P =/= NP! :p

Reply on news.ycombinator.com