## 0287: "NP-Complete"

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

Moderators: Moderators General, Prelates, Magistrates

space_raptor
Posts: 1497
Joined: Fri Nov 17, 2006 5:02 pm UTC
Location: Calgary
Contact:
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
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
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
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:
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.

wing
the /b/slayer
Posts: 1876
Joined: Tue May 29, 2007 5:56 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.

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.

UmbrageOfSnow
Not Fully Human
Posts: 354
Joined: Sun Apr 22, 2007 7:06 am UTC
Location: Insomnia Island
Contact:
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.

Omniferous
Posts: 7
Joined: Wed Jul 04, 2007 4:56 am UTC
I would have given the answer, but I believe you have my answer.

voodooKobra
You just....
Posts: 159
Joined: Mon Mar 12, 2007 4:34 am UTC
Contact:
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

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 ]

Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand
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.

SpitValve
Not a mod.
Posts: 5130
Joined: Tue Sep 26, 2006 9:51 am UTC
Location: Lower pork village
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.

McHell
Posts: 322
Joined: Fri Jun 22, 2007 12:52 pm UTC
Location: Ellowen Deeowen
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.

PotatoEngineer
Posts: 17
Joined: Fri Oct 20, 2006 10:57 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
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.

6453893
Posts: 557
Joined: Wed Dec 13, 2006 2:40 am UTC
Location: Australia
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
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"

necroforest
Posts: 195
Joined: Tue Apr 10, 2007 3:46 pm UTC
Contact:
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
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
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.

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

### Re: Solution

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.

Belial
A terrible sound heard from a distance
Posts: 30450
Joined: Sat Apr 15, 2006 4:04 am UTC
Contact:
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
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

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

devnull
Posts: 1
Joined: Mon Jul 09, 2007 2:20 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:
rembooo, your webpage wont come up, why that is?

JoshuaZ
Posts: 401
Joined: Tue Apr 24, 2007 1:18 am UTC
Contact:
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).

Tractor
Posts: 2467
Joined: Mon Jan 08, 2007 6:17 pm UTC
Location: no
ehiunno wrote:rembooo, your webpage wont come up, why that is?

It's true. It was working earlier, but died.
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:

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

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

You aren't the only one.

thesilentpyro
Posts: 189
Joined: Mon Jul 09, 2007 3:08 pm UTC
Location: In the ashes, dancing with the flames
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:
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:
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:
bagh, it wasn't working for me either but it worked before.

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

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

ehiunno
Posts: 220
Joined: Mon Jun 25, 2007 3:46 pm UTC
Location: NN, VA
Contact:
awesome, thanks for that necrofest. Chalk that up to the myriad of things I didn't know google could do.

dekonstruct
Posts: 38
Joined: Tue Jan 30, 2007 6:52 pm UTC
Location: Western New York
Contact:
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.

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.
at least five of the previous posters need to POST IN THE INTRO THREAD OR PERISH!!!

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
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
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
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.

Sprocket
Seymour
Posts: 5951
Joined: Mon Mar 26, 2007 6:04 pm UTC
Location: impaled on Beck's boney hips.
Contact:
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”

Zohar wrote: Down with the hipster binary! It's a SPECTRUM!