0287: "NP-Complete"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

User avatar
space_raptor
Posts: 1497
Joined: Fri Nov 17, 2006 5:02 pm UTC
Location: Calgary
Contact:

Postby space_raptor » Mon Jul 09, 2007 5:56 am UTC

Alright. What does NP-complete mean?
The drinking will continue until morale improves.

Fiddly
Posts: 6
Joined: Mon Mar 12, 2007 1:56 am UTC

Postby Fiddly » Mon Jul 09, 2007 6:06 am UTC

I thought the knapsack problem is maximizing utility subject to capacity constraints. The problem described here seems a bit different.

Brom
Posts: 4
Joined: Mon Jul 09, 2007 6:00 am UTC

Postby Brom » Mon Jul 09, 2007 6:06 am UTC

I used the Traveling Salesman approach that was mentioned.

And I got 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wings.

So 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wing equals $11.80. If one were to also add the sticks, then the price would be too much, so I also added sales tax and tip to the equation. With 5 cents as tax, then its $11.85. They would then tip $3.20 to get to final amount.

Karrion
Posts: 92
Joined: Fri Jun 22, 2007 12:14 am UTC
Location: Melbourne, AU

Postby Karrion » Mon Jul 09, 2007 6:26 am UTC

Fiddly wrote:I thought the knapsack problem is maximizing utility subject to capacity constraints. The problem described here seems a bit different.


It's NP complete, so it can be translated into any other NP complete problem (in polynomial time), including subset sum (the obvious one), knapsack, travelling salesman, etc.

wocket
Posts: 87
Joined: Thu Jun 28, 2007 3:41 am UTC
Contact:

Postby wocket » Mon Jul 09, 2007 6:44 am UTC

Brom wrote:I used the Traveling Salesman approach that was mentioned.

And I got 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wings.

So 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wing equals $11.80. If one were to also add the sticks, then the price would be too much, so I also added sales tax and tip to the equation. With 5 cents as tax, then its $11.85. They would then tip $3.20 to get to final amount.

I don't really see how this is a viable solution, since the server was instructed to bring out EXACTLY $15.05 worth of appetizers, and there was no way they could know what their tip would be beforehand.

User avatar
wing
the /b/slayer
Posts: 1876
Joined: Tue May 29, 2007 5:56 am UTC

Postby wing » Mon Jul 09, 2007 6:48 am UTC

Alky wrote:
oblivimous wrote:Reading up on the travelling salesman reminded me of a something I've wondered for a while: What method do Google maps, MapQuest, etc. use to find the fastest possible route?


They probably use an external memory algorithm, because all of the data might not fit in memory. Interestingly, a lot of problems get a lot harder when you count I/Os instead of operations: most linear-time algorithms in the RAM model take sorting complexity in the I/O model.

What's even more interesting about this is the lack of a wikipedia article.
Actually, the INITIAL pathing data returned by Google Maps was outright purchased from another company along with the map data and the pathing is revised over time as queries are performed.

For instance, you'll query up a certain route, and Google will start with the vendor-provided path, and then recursively try to find a better route for each "leg". It'll spend a given amount of time trying to figure this out, and then give you what it has in the interests of responsiveness. It'll then store the changes and continue revising as queries overlap the one you made. There may also be a 24/7 optimizer running.

So, each return isn't guaranteed to be optimal, but the more often a route is "traveled", the more optimized it will become. This allows an absolute minimum of precomputing to be done (in other words, no, there is no giant supercomputer that calculates every possible route from a-b) and still produces very accurate results pretty quickly (Because most Google Maps queries are actually pretty short, it may be able to perform the full optimization in the first shot). No insane amounts of I/O necessary. Just read in the existing path data, and the road data within a certain distance of the path, which is a pretty small amount of data.

User avatar
UmbrageOfSnow
Not Fully Human
Posts: 354
Joined: Sun Apr 22, 2007 7:06 am UTC
Location: Insomnia Island
Contact:

Postby UmbrageOfSnow » Mon Jul 09, 2007 6:54 am UTC

wocket wrote:
Brom wrote:I used the Traveling Salesman approach that was mentioned.

And I got 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wings.

So 1 mixed fruit, 1 french fries, 1 side salad, and 1 hot wing equals $11.80. If one were to also add the sticks, then the price would be too much, so I also added sales tax and tip to the equation. With 5 cents as tax, then its $11.85. They would then tip $3.20 to get to final amount.

I don't really see how this is a viable solution, since the server was instructed to bring out EXACTLY $15.05 worth of appetizers, and there was no way they could know what their tip would be beforehand.


Also, this doesn't even seem solution-like. You shouldn't be able to just fudge away everything with tax and tip, or it isn't really a puzzle at all, just a cost of dinner. And how is that a "Traveling Salesman approach"? I mean did he make a weighted graph somewhere in there that I missed?
yellie wrote:Confession: I just had to look up the word ubiquitous because I kept seeing it all over the place and had no idea what it meant.

User avatar
Omniferous
Posts: 7
Joined: Wed Jul 04, 2007 4:56 am UTC

Postby Omniferous » Mon Jul 09, 2007 6:54 am UTC

I would have given the answer, but I believe you have my answer.

User avatar
voodooKobra
You just....
Posts: 159
Joined: Mon Mar 12, 2007 4:34 am UTC
Contact:

Postby voodooKobra » Mon Jul 09, 2007 7:09 am UTC

blind visionary wrote:I'm so glad that when I come here, I find a bunch of other people who's first thought is to try and solve it.

Seconded.
If you need to reach me, email kobrasrealm@gmail.com

in b4 spam

Kobra's Corner - My horribly-written opinions that aren't worth reading. Seriously; you're better off reading Nietzsche translated into myspace user lingo.

spacedman
Posts: 19
Joined: Fri Mar 02, 2007 9:58 am UTC

Solution

Postby spacedman » Mon Jul 09, 2007 7:27 am UTC

I have a truly marvellous general solution to these classes of problem but this textbox is too narrow to contain it.

Barry

[no, you guys DONT need a hint to know what I'm talking about here :)]

User avatar
Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

Postby Mouffles » Mon Jul 09, 2007 7:36 am UTC

It's interesting that if the total had been $15.00 or $15.10, the problem would have a unique solution.
In the spirit of taking things too far - the 5x5x5x5x5 Rubik's Cube.

User avatar
SpitValve
Not a mod.
Posts: 5130
Joined: Tue Sep 26, 2006 9:51 am UTC
Location: Lower pork village

Postby SpitValve » Mon Jul 09, 2007 7:47 am UTC

wing wrote:Actually, the INITIAL pathing data returned by Google Maps was outright purchased from another company along with the map data and the pathing is revised over time as queries are performed.

For instance, you'll query up a certain route, and Google will start with the vendor-provided path, and then recursively try to find a better route for each "leg". It'll spend a given amount of time trying to figure this out, and then give you what it has in the interests of responsiveness. It'll then store the changes and continue revising as queries overlap the one you made. There may also be a 24/7 optimizer running.

So, each return isn't guaranteed to be optimal, but the more often a route is "traveled", the more optimized it will become. This allows an absolute minimum of precomputing to be done (in other words, no, there is no giant supercomputer that calculates every possible route from a-b) and still produces very accurate results pretty quickly (Because most Google Maps queries are actually pretty short, it may be able to perform the full optimization in the first shot). No insane amounts of I/O necessary. Just read in the existing path data, and the road data within a certain distance of the path, which is a pretty small amount of data.


You reckon? That'd probably mean asking directions to rural towns in NZ is not going to be very well optimised. It also sounds like quite a bit of data to store...

Edit: Nah, I don't think it stores the most optimal route from A to B: it seems to consistently take longer for longer trips than shorter ones, implying that it's calculating it each time.

User avatar
McHell
Posts: 322
Joined: Fri Jun 22, 2007 12:52 pm UTC
Location: Ellowen Deeowen

Postby McHell » Mon Jul 09, 2007 9:36 am UTC

jakerg22 wrote:I'm not sure if it takes stoplights into account, or stop signs, or if it gives preferential treatment to interstates and highways.


They do take lights into account; sometimes you see a suggested route that turns one street before a target (right-left-right), instead of simply straight to target (right) if the target's corner has a stoplight.

If the blocks are rectangular (or parallellograms, true) then the suggested speed x length comes to the same, so avoiding the light is what it suggests. But the two extra corners and unforeseeable-traffic (a parking car? a bike? a kid?) slows you down more than the light.

I was going to attach a picture of a routeplanner doing this, in a street I used to live, but it now suggests something else --- a longer route avoiding 2 streetlights.

User avatar
PotatoEngineer
Posts: 17
Joined: Fri Oct 20, 2006 10:57 am UTC

Postby PotatoEngineer » Mon Jul 09, 2007 9:41 am UTC

SpitValve wrote:Edit: Nah, I don't think it stores the most optimal route from A to B: it seems to consistently take longer for longer trips than shorter ones, implying that it's calculating it each time.

The approach described works for both long routes and short ones; if the route is broken into several legs, and each leg is processed separately, you should expect a longer total time for longer trips.

jonas
Posts: 37
Joined: Mon Mar 26, 2007 6:12 pm UTC

Postby jonas » Mon Jul 09, 2007 9:47 am UTC

I brute-forced the solution too (after verifying that there are few enough possibilities that it can be done). I made an error so I didn't get the seven mixed fruit solution until I checked the forums, but I've corrected the error now.

User avatar
6453893
Posts: 557
Joined: Wed Dec 13, 2006 2:40 am UTC
Location: Australia

Postby 6453893 » Mon Jul 09, 2007 9:48 am UTC

I like to give my waiters quadratics to solve. As in, "We'll take three of dessert X and two of Desert Y, where 5X^2-X+$5 Tip=2Y^2-4Y+$3 Tip."

After I've been to a restaurant once, the waiters always keep a decent calculator handy.

frodo34x
Posts: 5
Joined: Wed Jun 06, 2007 7:06 pm UTC

Postby frodo34x » Mon Jul 09, 2007 9:50 am UTC

archgoon wrote:Question, do we need to factor in the variable tip?

Also, it's only about 8^6 possibilities. Brute force it.

Why would you factor in the tip? The tip can be any amount you want, so you could just say "1 hot wings and an $11.50 tip"

User avatar
necroforest
Posts: 195
Joined: Tue Apr 10, 2007 3:46 pm UTC
Contact:

Postby necroforest » Mon Jul 09, 2007 11:26 am UTC

I'm suprised nobody has pointed this out - The problem isn't NP-Complete, since it's not a decision problem, therefore not in NP.

Also, I figured that google maps would just use the Floyd-Warshall algorithm (all-pairs shortest path; finds the shortest path between every two pairs of vertices, complexity Theta(n^3) ) once on the dataset and be done with it, although now that I think about it n^3 complexity might be pretty rough for that big of a data set (plus the not-fitting-in-memory thing), especially since most of those routes would never be looked at (your house-> every other house in your neighborhood, and reverse dirrections)

bippy
Posts: 189
Joined: Sun Jan 28, 2007 5:49 am UTC

Postby bippy » Mon Jul 09, 2007 12:33 pm UTC

This would have been a funny comic except that it reminds me of buying food as a broke college student. "I have fifteen dollars and I need as much food as possible, at least one portion of which cannot be Ramen."

Bugsy
Posts: 2
Joined: Mon Jul 09, 2007 12:35 pm UTC

Postby Bugsy » Mon Jul 09, 2007 12:54 pm UTC

blind visionary wrote:I'm so glad that when I come here, I find a bunch of other people who's first thought is to try and solve it.
I'm not as glad that I found the people who try to solve it (no offense, of course), I'm just glad that someone posted the solution so I don't have to spend my time solving it. As soon as I read the strip I was cursing Randall for forcing me to come up with a general solution. As it turns out I'd be happy turning in chessguy's work. But I really want to know how he's going to tip me seven fifty-two and a half.

And I really don't like to talk about my flair.

User avatar
Arancaytar
Posts: 1642
Joined: Thu Mar 15, 2007 12:54 am UTC
Location: 52.44°N, 13.55°E
Contact:

Re: Solution

Postby Arancaytar » Mon Jul 09, 2007 1:05 pm UTC

spacedman wrote:I have a truly marvellous general solution to these classes of problem but this textbox is too narrow to contain it.


Any forum where Fermat's Last Theorem is considered as good a pop culture reference as All Your Base is a place I want to find out more about. :)

User avatar
Belial
A terrible sound heard from a distance
Posts: 30450
Joined: Sat Apr 15, 2006 4:04 am UTC
Contact:

Postby Belial » Mon Jul 09, 2007 1:10 pm UTC

My response to this would be to bring them the mixed fruit, and inform them that they're paying $15.05 for it.
addams wrote:A drunk neighbor is better than a sober Belial.


They/them

Remboooo
Posts: 5
Joined: Mon Jul 09, 2007 1:24 pm UTC

Postby Remboooo » Mon Jul 09, 2007 1:26 pm UTC

Ok, I'll admit it - I spent my morning coding a solver for this. It's available at http://rembo.is-a-geek.net/knapsack.php :roll:

And yes, you'll have to feed it the prices in cents.

devnull
Posts: 1
Joined: Mon Jul 09, 2007 2:20 pm UTC

Postby devnull » Mon Jul 09, 2007 2:24 pm UTC

1: Remboooo you aught to put some sensible limits on your php script...

2: Prolog n00b ftw:

Code: Select all

app(A,B,C,D,E,F):-
 member(A,[0,1,2,3,4,5,6,7]), %MixedFruit
 member(B,[0,1,2,3,4,5,6,7]), %FrenchFried
 member(C,[0,1,2,3,4,5]),     %SideSalad
 member(D,[0,1,2,3,4]),       %HotWings
 member(E,[0,1,2,3]),         %MozzarellaSticks
 member(F,[0,1,2]),           %SamplerPlate
 S is A*215 + B*275 + C*335 + D*355 + E*420 + F*580,
 S = 1505.

ehiunno
Posts: 220
Joined: Mon Jun 25, 2007 3:46 pm UTC
Location: NN, VA
Contact:

Postby ehiunno » Mon Jul 09, 2007 2:35 pm UTC

rembooo, your webpage wont come up, why that is?

JoshuaZ
Posts: 401
Joined: Tue Apr 24, 2007 1:18 am UTC
Contact:

Postby JoshuaZ » Mon Jul 09, 2007 2:46 pm UTC

space_raptor wrote:Alright. What does NP-complete mean?


Non-rigorous explanation.

Definition: A decision problem is a question which has a yes or no answer for some general set of input. An example would be "is n prime?"

A decision problem is said to be in P if there is an algorithm that solves the problem in time bounded above by a polynomial functions of the length of the input (for an integer, that is essentially log n (if we write in base 2, that is log_2 n, base 10 log_10 n, but since changing base will only alter the value of the log by a constant multiple, the base we use is irrelevant).

A decision problem is said to be in NP if when the problem has an answer of yes, there is a proof of the answer which can be verified in polynomial time. For example, "is n composite" is in NP since the proof is simply presenting some non-trivial factor of the number which can be checked by long division.

A problem P_1 is said to be NP-hard if there is a polynomial time algorithm which will reduce any problem P_2 in NP to an equivalent problem in P_1.

A problem is said to be NP-complete if it is in NP and is NP-hard.

It is unknown if P=NP or not, but most computer scientists suspect that they are unequal. There is a million dollar prize for resolving the problem.
We care about these problems for a variety of reasons including being related to cryptography (for example factoring in NP).

User avatar
Tractor
Posts: 2467
Joined: Mon Jan 08, 2007 6:17 pm UTC
Location: no

Postby Tractor » Mon Jul 09, 2007 3:08 pm UTC

ehiunno wrote:rembooo, your webpage wont come up, why that is?

It's true. It was working earlier, but died.
May be linked to:
1: Remboooo you aught to put some sensible limits on your php script...
9 x 6 = 42

Note: Randall kicks ass.

MissingDividends
Posts: 161
Joined: Fri May 25, 2007 8:59 pm UTC
Location: Cambridge, MA
Contact:

Re: The Haskell answer

Postby MissingDividends » Mon Jul 09, 2007 3:11 pm UTC

toysbfun wrote:
chessguy wrote:There are only 2 solutions:
Prelude> let g = [0..10] in [[a,b,c,d,e,f] | a <- g, b <- g, c <- g, d <- g, e <
- g, f <- g, abs(a*2.15+b*2.75+c*3.35+d*3.55+e*4.2+f*5.8-15.05)<0.001]
[[1.0,0.0,0.0,2.0,0.0,1.0],[7.0,0.0,0.0,0.0,0.0,0.0]]

That is:
1 Mixed Fruit, 2 Hot Wings, 1 sampler plate, (EDIT: already mentioned) or
7 Mixed Fruit (already mentioned)


I feel like I was cheated in my math classes..


You aren't the only one.

User avatar
thesilentpyro
Posts: 189
Joined: Mon Jul 09, 2007 3:08 pm UTC
Location: In the ashes, dancing with the flames

Postby thesilentpyro » Mon Jul 09, 2007 3:12 pm UTC

I caused myself ten minutes of headache when I tried solving it with the assumption that most people, like myself and my family, never order more than one of the same kind of appetizer due to the desire to get more variety for the money. It was only when I couldn't come up with any solution that way that I wrote an Excel macro to do the work for me.
Today is more fun if you leave tomorrow behind.

ehiunno
Posts: 220
Joined: Mon Jun 25, 2007 3:46 pm UTC
Location: NN, VA
Contact:

Postby ehiunno » Mon Jul 09, 2007 3:19 pm UTC

JoshuaZ wrote:It is unknown if P=NP or not, but most computer scientists suspect that they are unequal. There is a million dollar prize for resolving the problem.


maaayyyyyybe...

mayyyyybe not: http://kryten.mm.rpi.edu/scb_pnp_solved22.pdf

Grant it, that paper is as of yet still pending publication, but the author is well respected.

JoshuaZ
Posts: 401
Joined: Tue Apr 24, 2007 1:18 am UTC
Contact:

Postby JoshuaZ » Mon Jul 09, 2007 3:21 pm UTC

ehiunno wrote:
maaayyyyyybe...

mayyyyybe not: http://kryten.mm.rpi.edu/scb_pnp_solved22.pdf

Grant it, that paper is as of yet still pending publication, but the author is well respected.


The link posted isn't working for me.

ehiunno
Posts: 220
Joined: Mon Jun 25, 2007 3:46 pm UTC
Location: NN, VA
Contact:

Postby ehiunno » Mon Jul 09, 2007 3:22 pm UTC

bagh, it wasn't working for me either but it worked before.

http://www.rpi.edu/~brings/

Thats where I got it, I dont know why it is down. Maybe google would turn up more info about the paper.

User avatar
necroforest
Posts: 195
Joined: Tue Apr 10, 2007 3:46 pm UTC
Contact:

Postby necroforest » Mon Jul 09, 2007 3:32 pm UTC


ehiunno
Posts: 220
Joined: Mon Jun 25, 2007 3:46 pm UTC
Location: NN, VA
Contact:

Postby ehiunno » Mon Jul 09, 2007 3:33 pm UTC

awesome, thanks for that necrofest. Chalk that up to the myriad of things I didn't know google could do.

User avatar
dekonstruct
Posts: 38
Joined: Tue Jan 30, 2007 6:52 pm UTC
Location: Western New York
Contact:

Postby dekonstruct » Mon Jul 09, 2007 3:36 pm UTC

Us liberal arts majors are a bit confused by this one. My wife is a server and I'm pretty sure she'd explode if someone asked her this (no I will not tell you where she serves I want her in one piece).

At least chotchkies reference was in there so I can still laugh my dumb little artsy head off.

User avatar
sillybear25
civilized syllabub
Posts: 435
Joined: Tue Jun 19, 2007 2:19 am UTC
Location: Look at me, I'm putting a meta-joke in the Location field.

Postby sillybear25 » Mon Jul 09, 2007 3:50 pm UTC

at least five of the previous posters need to POST IN THE INTRO THREAD OR PERISH!!! :evil:

Oh, and I liked the comic. :)
This space intentionally left blank.

oblivimous
Posts: 139
Joined: Tue Nov 07, 2006 6:36 pm UTC
Location: Fremont, CA

Postby oblivimous » Mon Jul 09, 2007 4:04 pm UTC

ok, so my only coding class was on basic in 10th grade high school, about 1993.

10 For a = 0 to 7
20 For b = 0 to 6
30 For c = 0 to 5
40 For d = 0 to 5
50 For e = 0 to 4
60 For f = 0 to 3
70 If 215a + 275b + 335c + 355d + 420e + 580f = 1505 then print a,b,c,d,e,f
80 next f
90 next e
100 next d
110 next c
120 next b
130 next a

Line numbers ftw, and mozerella sticks = 420

pfargtl
Posts: 16
Joined: Thu May 10, 2007 5:54 pm UTC
Location: Illinois

Postby pfargtl » Mon Jul 09, 2007 4:04 pm UTC

I'm pretty sure Google maps gives preferential treatment to interstates and highways.

I once wanted a map from my house to another house across town (c. 100,000 people in my town... it's not too large)...

I ran the query, and google wanted me to get on the interstate just to get across town. Ridiculous.
What the Pfargtl?

mootinator
Posts: 69
Joined: Mon Mar 26, 2007 10:27 pm UTC
Location: Saskatoon, SK

Postby mootinator » Mon Jul 09, 2007 4:30 pm UTC

necroforest wrote:I'm suprised nobody has pointed this out - The problem isn't NP-Complete, since it's not a decision problem, therefore not in NP.


Absolutely. The NP-Complete problem is determining whether a solution exists. As such a smart waiter would realize that the annoying clients already KNOW there's a solution, beat it out of them, THEN go figure out an alternate solution, and bring them 7 mixed fruit instead of the 1 mixed fruit, 2 hot wings, and 1 sampler plate the pretentious bastards actually wanted.

User avatar
Sprocket
Seymour
Posts: 5951
Joined: Mon Mar 26, 2007 6:04 pm UTC
Location: impaled on Beck's boney hips.
Contact:

Postby Sprocket » Mon Jul 09, 2007 4:38 pm UTC

XKCD wrote:General solutions get you a 50% tip


General results - Randall gets a glass of dishwater.

ALT TEXT

General results - Waiter gets fired for assault.



Also: should i include that 50% tip into the soltuion or a .05% Massachusettes prepared food tax?
Last edited by Sprocket on Mon Jul 09, 2007 5:05 pm UTC, edited 2 times in total.
"She’s a free spirit, a wind-rider, she’s at one with nature, and walks with the kodama eidolons”
Image
Image
Image
Image
Image
Zohar wrote: Down with the hipster binary! It's a SPECTRUM!


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: No registered users and 34 guests