![[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
|
FYI I can see the significance of Prowee’s emergencies. The guy that was whistling while walking away and the person talking to Richard look like entirely different individuals.
A boxy shape for the talker’s hair, the talker looking overweight, and the talker having a beard aren’t matching up with the whistler’s thin, teenaged, bowl-cut physique.
So I can see how bad this is going for Prowee. My best wishes to her family, and to her as an individual. Sorry to the artist for bringing this up.
So… either they’ll hate each other on sight.
Love each other on sight.
Or both. Starting from hate and ending with love.
Let’s find out.
Team P!=BPP ftw, which would imply P!=NP
or Team P=BPP ==> BPP!=NP, also P!=NP
yay
@ Yuko Hoon:
At first glance it seems like a match made in the Mainfram yes
<a href="#comment-99164" title="Poor Sandra. If things get heated enough, she is going to have a step-mom. =D
If so, poor Meldoy Crawford.
If she thinks this problem can’t be solved, what will she think of Woo ?
Love is in the aiiir.
Onihikage wrote:
Quantum computers aren’t magic. There’s no proof and no reason to believe BQP includes NP (any more than the opposite, at this point).
TSP has been “solved” in practical use in that it can be approximated to within 1% error. The results are already used in logistics and chip manufacturing, for example. But solving the problem with 0% error is still NP-hard and thus equivalent to being able to solve any NP-hard problem.
roguebfl wrote:
“Safe” key lengths increase every year, though, so you shouldn’t ever assume your encrypted secrets to stay safe more than 10 years or so (provided there’s a dedicated attacker).
Thanks for this. I saw the “Team P==NP” shirt and smiled. One of my favourite CS profs spent much of his career working for that team. But then I saw the other shirt, and I just laughed.
Personally, I believe P != NP, but P == NP would make the world so much more interesting.
@ Wevah:
For XOR you could write either the derived symbol⊕ or type the full equation using only ands ors and nots.
Therefore:
GO TEAM (((P == NP) ∨ (P != NP)) ^ ¬((P == NP) ^ (P != NP)))
kazunori wrote:
And I botched it. Mixing notations… Team (((P == NP) ∨ (P != NP)) ^ !((P == NP) ^ (P != NP)))
@ Arbiter:
I think you mean Velma. Does kinda resemble her.
@ Walter Matera:
It’s nice to know I’m not the only one out there whose more interested in working out what song is being transcribed whenever musical notation is randomly shown.
@ Anonymouse:
i also think she may be a potential love interest… i hope so….
@ nameless:
Amen, sir.
[ERROR] wrote:
Nah, it makes perfect sense. The single equals in C is an assignment. That would be Richard defining P to be NP. And while just defining logical truths is extremely brazen, it’s also quite pointless.
Richards shirt just requires the assumption that people prefer to print statements on shirts that they believe evaluate to “true”.
Shouldn’t the developer be wearing the P!=NP shirt since he’s going to be demanded to come up with those solutions instead of the graphics person?
Note to Oliver: “beziehungsweise” is not always translated as “respectively”, which is really only used to pairwise match elements of one list to each other (e.g. “For breakfast, lunch and dinner I had eggs, bread and cheese, respectively”). In cases such as the post below the comic, “and” or “or” or sometimes “and/or” are used. In this case “and” would be most correct.
As a software developerette (yes, I do exist) AND Sandra and Woo Lover, there’s only one thing for me to say about the prospect of more “Sandra and Woo IT Comics”:
YIPPIE!!!!!!!!!1einself
The employee in the first two panels looks like an anime character(s) I’ve seen a few times.
I concur. 😉
@ sophie d.:
was meant to be an answer to ricky picky ricky’s comment
Ahah, just now decided to play the tune in the last panel. Turns out he’s whistling the mortal combat theme song… xD
Huh, until we have Carcheve 2 level computing recourses, the question is not even worth pondering, outside the more subtle kinds of Sci Fi, such as Battle Angel Alita, which can make even the most esoteric corners of scientific thought freaky cool.
@ realbrickwall:
It’s close as far as intervals. If it was meant to be, then the third note would have had to have been lowered one scale down, along with the other notes that don’t repeat the first two.
I need a shirt like this. Not saying which side I’m on, only that I need one of those shirts.
@ Kirbilius Clausius:
Only if the developer is a constructivist.
A constructivist would be interested in the truth of (P==NP) || (P !=NP)
A contructivist will not accept a disjunction without being able to decide which disjunct holds.