One of my all time favorite blog entries is a truly epic tale of dating gone wrong that culminates in the strangest reference to P=NP you'll probably ever encounter.
I also have a feeling (intuition at work) that Jeff is taking some part-time classes to fill the gaps. We will know when we see his first turing machine in the blog post, which is the frankenstein of pure math (and just as lovely).
Jeff knows “quantity > quality”, and to “always be jabbing”, and… he’s absolutely right. Hence this post = win, as the others before. Just a simple man still doing what he loves, his faith in community and commenters to guide him, even the detractors. Bravo Jeff, bravo, I look forward to every article.
@ Chistopher Galpin: “Jeff knows ‘quantity > quality’”
Unless of course you are just talking about blogging and using the readers to generate hit counts and thus ad revenue, in which case we should just boycott the blog as I find that insulting. In any case, I should probably stop wasting my time reading Jeff’s blog - it is useless.
For those wanting to try this at home, here’s a little solution using Choco (using Groovy):
import static choco.Choco.*
import choco.kernel.model.variables.integer.IntegerVariable
def m = new choco.cp.model.CPModel()
def s = new choco.cp.solver.CPSolver()
def menu = [
‘Mixed fruit’ : 215,
‘French fries’ : 275,
‘Side salad’ : 335,
‘Hot wings’ : 355,
‘Mozzarella sticks’ : 420,
‘Sampler plate’ : 580
]
def vars = new IntegerVariable[menu.size()]
def coeffs = new int[menu.size()]
def sum = 1505
menu.eachWithIndex { k, v, i ->
vars[i] = makeIntVar(k, 0, sum.intdiv(v))
coeffs[i] = v
}
m.addConstraint(eq(scalar(coeffs, vars), sum))
s.read(m)
def more = s.solve()
while (more) {
println "Found a solution:“
vars.each {
def v = s.getVar(it)
if (v.val) println " $v.val * $v.name”
}
more = s.nextSolution()
}
I didn’t understand a thing. I haven’t done any math courses and I’m a working programmer. I just code all day retrieving shit from the database through some SELECT shit FROM BigPile and load some crap into the database INSERT INTO BigPile(shit) VALUES(‘lots of shit’).
That seems to do the trick. Obviously this kind of programming is too advanced to my boss, so I’m considered somewhat of an expert in my office, (or I think so anyway…).
The last article Jeff did on NP was full of people trying to slowly and carefully explain it to him, with the occasional comment from Jeff that was equivalent to him sticking his head in the sand.
And so after expressing what amounts to willing ignorance on the subject it’s interesting to see Jeff climb back into the saddle.
Of course, last time he restated that there’s an implicit “I may not know what I’m talking about, this is all a learning exercise for me”. Which is really really implicit, considering the writing style strongly suggests otherwise.
There’s no Amazon affiliate link to a book he hasn’t read this time, so at least he is learning something.
Anyhow, one less thing for my feed reader to check. The more people keep coming back after posts like this, the more posts like this there’ll be. I’m living in fear of the day that I have to reeducate people I meet in the workplace who learned their CS theory from here.
First.
@Dave, you are absolutely correct. Lot of people who want to learn from these posts will just go home with buzz words, superficial concepts and usually incorrect and misleading statements about the problem. They may be turned off by the subject, maybe wont ask the important questions regarding the subject. People like Jeff Atwood should be ashamed of misusing their clout. Thank God there are people like Michael Sipser, who are genuinely interested in the problem and educating students about it. I dont know if Jeff Atwood even cares about the comments here but linking xkcd, copy pasting from a book, making worthless comments is not just a waste of every body’s time but just plain wrong.
Second?
Gotta love math.
Bah. I proved that P == NP and P != NP on Stack Overflow (see 900564).
1 Mixed Fruit, 2 Hot Wings and a Sampler Plate.
“The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible.”
This is obviously some strange usage of the word “defining” that I hadn’t previously been aware of.
Or seven mixed fruit.
NP problems can be solved feasibly by a computer as long as the input is sufficiently small
The easiest is still 7 rounds of mixed fruit.
“The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible.”
That doesn’t make sense optimal solutions are possible. It just takes exponentially longer as the input size increases.
You made the classic mistake of pasting an xkcd cartoon with the tooltip. The tooltip is part of the fun.
Are you seriously going to post another thing about P=NP? Really? No, really? I don’t know what this weird story about some guy dating a compulsive liar has to do with anything … I’m flummoxed and I’ve never been flummoxed before.
“The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible.”
Three problems with this:
There’s no guarantee that a polynomial-time algorithm for an NP-complete problem would require math that we don’t know yet.
It’s not the defining characteristic, since problems in supersets of NP are even more time-consuming.
Every problem in NP is computable, so actually, you can find an optimal solution, even if it takes a while.