Notes on the final
December 13th, 2008* A note on Q3 in the final. You will be able to give your answer using a from-first-principles explanation. you will NOT need to invoke theorems beyond the simple “X is NP-Complete” kind.
* On Q2, you are allowed super-linear preprocessing time (i.e you can sort if you want)
Entries
December 13th, 2008 at 8:04 pm
On the Q3 note, does that mean that we really don’t need to prove anything for the problem (as in everything has been proven already in class or in the book)?
December 13th, 2008 at 8:17 pm
oh you need to make some kind of argument that involves mathematical manipulation.
December 13th, 2008 at 8:18 pm
“from first principles” means that you don’t need to invoke any external results: you can prove anything you need directly
December 14th, 2008 at 8:11 pm
on Q2 is our preprocessing time allowed to be made before or after the query q has been asked, or should we state this assumption in our answer?
December 14th, 2008 at 8:16 pm
preprocessing happens BEFORE any query arrives. so here’s how it works.
the input n numbers are presented
you do preprocessing
while( read a query q) {
process q
}
it’s the step inside the while loop that must have the target running time.
December 14th, 2008 at 9:42 pm
Do you mean “directly from the problem descriptions of Knapsack and VC”, or do you mean “directly from the known best running times of Knapsack and VC”?
December 14th, 2008 at 9:43 pm
ahh. I mean from the problem descriptions. Basically I’m treading very carefully so as not to reveal the answer accidentally
December 14th, 2008 at 9:58 pm
I figured.
Thanks, that should help me gain some insight.
December 14th, 2008 at 10:39 pm
Let me be even clearer on Q3, since I’m getting some questions about it. You may NOT do things like “blah blah problem is hard to approximate” UNLESS you are able to actually prove that this is the case. No citing of PCP theorems, APX, or what not. If you want, you can pretend that you’re doing this final in 1981, well before the advent of the idea of hardness of approximation.
December 14th, 2008 at 11:04 pm
Could you give us your “official” versions of the problem descriptions?
December 14th, 2008 at 11:06 pm
am not sure I follow.
December 14th, 2008 at 11:13 pm
I mean for VERTEXCOVER and KNAPSACK. (ie, decision version? optimization version?) There are different version of both problems scattered about the text.
December 14th, 2008 at 11:15 pm
well they are both the optimization versions: for vertex cover it’s obvious (given G, etc etc). For KNAPSACK, you’re given “sizes” and “profit” and knapsack capacity and you want to maximize “profit” while keeping “size” below the knapsack capacity.
I can assure you that the subtle variations in definition have nothing to do with the answer.
December 14th, 2008 at 11:35 pm
I was wondering if Alice has really proven P=NP, since her running time has epsilon in it, but epsilon is encoded in log(epsilon) bits, is her algorithm not psuedo-polynomial?
December 14th, 2008 at 11:37 pm
With PTASs, you usually ignore the complexity of epsilon, because epsilon is “given in advance”: that’s why a PTAS is an approximation “scheme”, rather than a single algorithm: there’s one algorithm for each fixed value of epsilon.
December 14th, 2008 at 11:50 pm
Can you please explain a bit on “from first principles” ??
December 14th, 2008 at 11:52 pm
well, that you don’t need to invoke theorems/results that you can’t prove directly yourself.
December 15th, 2008 at 1:13 am
For problem 1, can we assume that we have a way of checking, in constant time, if the number our algorithm selects is in fact a valid epsilon median?
December 15th, 2008 at 1:33 am
you can assume whatever you like, as long as you prove that the assumption holds true. So in this case, you’d need to show me a routine that verifies that a given number is in fact an eps-approximate median in constant time
December 15th, 2008 at 5:59 pm
whew
December 16th, 2008 at 2:41 am
Hi, Prof, although the final is over, we still feel it would be grt if we could know the solution to the problem that we haven’t figure out since learning new things never ends.
December 16th, 2008 at 2:52 am
oh absolutely. I was giving you all a break before I posted the solutions