![[0672] Mortal Kombat](/comics/2015-04-03-0672-mortal-kombat.png "[0672] Mortal Kombat")
Although I’m a software developer, I’ve done only two strips about computer science resp. programming so far: Software Engineering, Now With Cats! and Cassandra. I hope you understand that I wanted to do a couple of strips about the topic eventually. This is the first of four strips in the series.
Richard’s and Melody’s t-shirts are about the P versus NP problem, the major unsolved problem in computer science. Here is a short explanation of the problem:
There is a class of decision problems, such as the travelling salesman problem, that can be solved by well-known algorithms. But all these algorithms need exponential time to find the solution, for example 2100 = 1,267,650,600,228,229,401,496,703,205,376 steps. This is, obviously, a lot and can’t be computed even on modern computers. After finding such a solution, only polynomial time is needed to verify that the solution is correct, for example 100² = 10,000 steps. This is usually very easy for a modern computer.
It is still an open question if algorithms exist that can also solve these decision problems in polynomial time. This would be a major breakthrough in computing and would make it possible to calculate exact results where only approximate solutions can be calculated today.
Richard thinks that this is possible, i.e. P == NP, while Melody thinks that this is impossible, i.e. P != NP.
- Jack: Uhm,… boss? Melody Crawford, the new department head of the graphics programming department, has just arrived.
- Richard: All right.
- Richard: Is it true that she headed M.I.T.’s robotics department for a while?
- Jack: Uhm,… yes.
- Richard’s t-shirt: TEAM P == NP
- Melody’s t-shirt: TEAM P != NP
|
Uh oh xD
I code in C++ but I have never heard of this… Well this should be good look forward to their reactions. Lol.
Never underestimate a gamers competitive streak…
uh, oh.
I detect some ‘friendly wars’ in the future.
If there’s one thing that ALWAYS livens things up in an office, it’s 2 gamers in the same game,but opposing factions.
Despite anyone not into gaming might think, gamers generally enjoy such situations and are quite sensible about them.
Having one the boss of the other will only hint at problems, but actually entice a closer relationship.
and if you don’t think gaming has anything to do with this, you haven’t thought enough about it.
the question among gamers is almost as old as computer (maybe older). we were facing the analog equivalent before then.
Soo, new reccuring character ? 🙂
(Should be pretty interesting seeing sandra meeting melody 🙂 (and awful for the other non math savvy characters ;))
Sooo…. what’s the age difference between the two of them?
As if anyone even remotely familiar with computing who is not a complete quack would think P==NP…
@ nameless:
Donald Knuth believes that P=NP; see here (question 17): http://www.informit.com/articles/article.aspx?p=2213858
I think they’ll get along just fine. I know I would.
The Big difference between the two teams is
if P == NP can be solved then modern encryption will crackable in a workable type period reading it obsolete but if P != NP is true a strong password with properly setup modern encryption is safe for the foreseeable future.
Oh it’s on now
This ..will… Or will not end well…
Could have been worse, could have been “Team Emacs” and “Team vi”…
They say that if you have to explain a joke, it’s a bad joke. That’s not true here. If the joke is nerdy enough that it needs to be explained, then it’s a good joke since it teaches us about stuff we didn’t yet know of!
Is that guy whistling the Peter Gunn theme bass line?
Welp… This will either end very well or very badly.
Let the sparks fly.
@ CptNerd:
False. Go “Team Nano”
@ realbrickwall:
realbrickwall wrote:
Yes it is. Computers I dunno much about but music I can read.
Well, considering quantum computing research has already reached a point where they figured out how to apply error correction to qubits without upsetting their quantum state via observation, I’d say that within a few decades we really will be able to solve the Traveling Salesman problem in polynomial time. Might just depend on how many qubits we can link up at once.
True!
@ CptNerd:
I am surprised by the number of people that get this. I think that is impossible to understand without a backround in engineering and/or CS. This says something about the crowd who reads “Sandra and Woo”
They’ll be dating in 6 months time….
Enigma wrote:
you think it’ll take that long? why?
TEAM (P == NP) ^ (P != NP)
(I know there’s no logical XOR, but I’m gonna fudge it.)
I’m a lifelong computer geek, so naturally I loved this.
Aside from the humor of the situation, they are likely to get along. They have more in common than otherwise; even though they are on opposite sides of the question, both care enough about the question to wear a T-shirt about it! There aren’t that many people out there who would care enough to do that.
I’m under the impression that this is to be his new gf.
Considering how they look at each other’s soft- and hardware (just reading the code of course) I can see they’ll have to spend quite some time together to work out this problem.
Does not take a computer to calculate that this may result in some core functionalties getting put together for the purpose of solving it.
The real question is how much processing time it will take to do so *grins*.
@ Anonymouse:
Is that really Thelma from Scooby Doo?
@ Anonymouse:
In other words, you are already shipping them.
@ Yuko Hoon:
Yep, dey gonna bang.
Lathiyades wrote:
I prefer a magnetized needle and a steady hand.
Team “P == NP is independent of theoretical computer science”. Just because that would be so mind-boggling.
@ Onihikage:
Quantum computing is considered “cheating”: the P/NP problem is defined mathematically, using theoretical model of computer. Quantum computing works differently, so results done with it don’t count.
Wait, there *are* computer scientists who believe NP==P?
(Well, on second thought there have to be some after the proof that NP==P is logically equivalent to markets being efficient; see Maymin, 2009)
How about you actually worked on way computer could solve problems analyticaly completly busting out the numerical solutions?
@ steveha:
Well I have a tshirt will Bill Gates quote – “the 640kB of memory should be sufficient for everyone”
(well he is right of course… I could live up even with less so it is Sufficient, it would just be boring)
I had not heard of this debate before. Thank you for sharing it with us!
I’m going to look it up and study it some more.
@ Paeris Kiran:
Did Bill Gates really say that 640K ought to be enough for everyone?
@ realbrickwall:
Almost. It’s missing a few sharps, unless those sharps were defined at the beginning of the piece.
I feel like I’m missing something here – a double-equals (“==”) generally acts as an “if equal” statement. From my interpretation, Richard isn’t wearing a statement/assertion so much as a boolean/conditional.
Can someone more seasoned than myself explain?
Oh, crapbaskets.
@ Arbiter:
Sure looks like her, doesn’t it? 😀
@ [ERROR]:
I had the same feeling, but you can assume they expect the condition to evaluate to true (why == and not =? well they are programmers and it makes one think of C)
@ nameless, Martin Cohen:
As long as it hasn’t been proven, I’d say each possibility is “possible”, though most of the computer scientists think that P≠NP. There are also several theorems stating that P=NP (or the polynomial hierarchy collapses at level at least k>=0 which is implied by P=NP) is equivalent to some property which “seems false but can’t be proven wrong”.
Well, it just means there are probably fewer people in the “P==NP team” but it doesn’t make sandra’s father an idiot (plus P=NP may have pretty fun consequences, so one may dream about it :p).
Love Richard’s kind of dumbfounded look.
New insta!ship. Melody and Richard are too geeky not to date.
Milestailsfox7 wrote:
You should have run across it in a class on Operations Research where they explore ways to create Efficient programs for computing things like UPS & FedEx drivers daily Delivery Schedules.
Trucking companies are always looking for a Better (ie Cheaper) way to get those trucks from Point A to Point B and Back to Point A.
And, the most “Obvious to the naked Eye” route is seldom the Cheapest.
.
steveha wrote:
Bill Gates is Rich enough to have Scrubbed all evidence that he ever said anything out of existence.
The Roots of the story go back to the design limitations in Windows and the PC Hardware at the time.
When the prices of Memory dropped enough that users could actually think about Installing more than that, they ran into a problem: Neither Windows Nor the Hardware available had any way to Address more memory than 640K.
In fact, it took a couple years and a Lot of very Kludgy Software to eventually get addressability to memory above 640K.
Eventually, Intel had to design a whole new class of CPU chips to free up the designers from the Addressability issues.
In fact, even now, Memory Management problems linger in Windows that can be traced back to those “Ancient” assumptions about, not so much how much people Need but how much memory people could Afford.
@ Walter Matera:
I think it’s supposed to be the Mortal Kombat theme, given the title of this comic.
There is going to be soooo much sparks between them! The world is going to crack before their heated tension, and the mantle of the Earth would crash into the depths of Hell!
Poor Sandra. If things get heated enough, she is going to have a step-mom. =D
It takes passion to delve fairly deep in the world of mathematics and science. You don’t get paid to develop new theories and algorithms unless they actually work or have a chance of making a lot of money, and more often than not your new ideas can end up exploding in your face, literally, and make you a liability until you make something cutting-edge above everything else.
High risk for a high reward, and a chance of not being to sustain oneself long enough to actually get that reward you so desire. You have to want it, bad.