Hacker News Reader

Comment by rocqua | Hacker News Reader

If all shots from storm troopers seem to barely miss, does that indicate that eventually we a storm trooper will miss? Or does it indicate a conspiracy among storm troopers to miss.

There are (apparantely) so many near misses for which it isn't clear why it should be a near miss. A great explanation for this near missing is the underlying fact that all NP problems contain some 'brute force' core that can never be polynomial.

Also note that the blog post does not at all concern your class UP. None of these are algorithms designed to be run. They are all about exploring abstract complexity classes.

View on HN

My point is stormtroopers:empire::UP:P

You're correct that stormtroopers will never hit, wrong that stormtroopers are representative of the empire, and wrong about the correlation between stormtrooper hits and empire hits, because you're ignoring higher order effects (eg, while stormtroopers always miss, the empire must hit something to be the "bad guy" -- and they do: Luke's parents, Alderaan, Obi-Wan, Hoth, Luke's arm, etc.

But purely from the existence of stormtroopers consistently missing, you can infer there's a Darth Vader that must score some hits, or the plot wouldn't work. I think we might be in a similar case for P ?= NP, and you're all way too blasse predicting from stormtroopers.

Very little research has been done on P - UP, where UP is all polynomials with degree less than 10,000 and coefficients less than 10^100.

In fact, I don't know a single P-UP algorithm that wasn't explicitly constructed to be -- do you?

I just think most of us are subtly talking about UP, not P. (Including the blog post.) And that you've incorrectly inferred a "plot" when all you've observed is "redshirt fire".

UP is much harder to deal with for a very simple reason. Composition of polynomials is still polynomial. Composition of polynomials of low degree leads to polynomials with high degree.

You keep assuming we only look at UP, whereas actually our theoretical work explicitly looks at P. Often, we don't even care about actual efficiency of the algorithm. The constants might be astronomical, but we still like the algorithm for its asymptotic properties.

I'm not versed in recent research, but I imagine the composition argument above often leads to polynomial performance with stupid degrees. I expect people only compute the actual degree when they thing it might be low.

Again though, this is not my field of research.

Reply on news.ycombinator.com