Re: University rank of Computer Architecture


In article <1175201073.655996.198190@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"MitchAlsup" <MitchAlsup@xxxxxxx> writes:
|>
|> > Both predictions are exponentially hard problems. Further tweaks
|> > will lead to minor gains, at most.
|>
|> Are they really this easy? I thought they were at least NP-complete.

NP complete problems are at MOST exponentially hard - and it is not
known if they are polynomial. So the term "exponentially hard" is
stronger than "NP complete", if a lot vaguer.

Branch prediction could be phrased to be NP complete, but I am not
sure that is the most useful formulation. You can certainly phrase
prefetch prediction to be more complicated than NP complete.


Regards,
Nick Maclaren.
.