4
$\begingroup$

Take for example the following sentence:

Computing a hash for a message is "easy"; retrieving the message from the hash is "hard".

Intuitively, I can perfectly understand what's written there. But, in mathematical terms, when is a problem considered hard and when is it considered easy?

I know that easy/hard should not be confused with "efficient", and I know that efficiency has to do with polynomial time complexity. Does it mean that hardness has nothing to do with asymptotic time complexity?

$\endgroup$
  • 2
    $\begingroup$ Likely this depends on the context. Usually, one can say a problem is easy if it can be solved in polynomial time. Similarly, a problem is said to be hard if there is no known polynomial time algorithm for it, e.g. the problem is say NP-complete. $\endgroup$ – Juho Sep 26 '15 at 16:49
  • $\begingroup$ In most cases "hard" means that its resource-need grows exponentially with the input (i.e. no essentially faster solutions as trial by one exist). But it is a highly inexact answer. $\endgroup$ – peterh - Reinstate Monica Sep 26 '15 at 19:50
5
$\begingroup$

They're not technical terms, so they don't have precise definitions. A problem is "hard" if it requires (or we think it requires) "large" computational resources to solve, and "easy" if it doesn't. "Large" depends on context but, in most contexts, a problem that can be solved in polynomial time is considered "easy".

$\endgroup$
  • $\begingroup$ I guess that's why, so far, I struggled to find something in the literature without luck. $\endgroup$ – Likk Sep 26 '15 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.