3
$\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?

Improve this question
$\endgroup$
3
  • 4
    $\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
    Commented Sep 26, 2015 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
    Commented Sep 26, 2015 at 19:50
  • $\begingroup$ There's difficult, and there's difficult, Asian style: anywhere between wouldn't know how to beyond machines&mortals. Is there any way to retrieving the message from [a fixed size] hash? (I wouldn't call something with length not dwarfed by message length for long messages a *hash.) $\endgroup$
    – greybeard
    Commented Dec 20, 2023 at 16:53

3 Answers 3

Reset to default
9
$\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".

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

I was taught in my Computer Science Algorithms class at IIT back in 1992 that "easy" problems are solved with a time/resource complexity of at worst X^3. This makes problems with solutions of x^4 or worse "hard" problems, as well as problems that have an exponential resource characteristic. But a "Google" search today does not provide for "hard" polynomial problems. Focus of "hardness" has been on NPC and NP-Hard for decades and the P vs. NP question.

Improve this answer
$\endgroup$
1
  • $\begingroup$ (You use both X and x, $n$ being more common.) $\endgroup$
    – greybeard
    Commented Dec 20, 2023 at 16:57
0
$\begingroup$

My definition: Its easy if my computer can find a solution within a few days. And it’s hard if my computer cannot solve it within six months.

That’s instances, not problems. The travelling salesman problem is easy for 20 nodes. Problems are easy / hard if interesting instances are easy / hard. Matrix multiplication is easy, but multiplying two 250,000 by 250,000 matrices is hard.

At some point you decide what’s easy / hard for you.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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