# What are the definitions for “hard problem” and “easy problem”?

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?

• 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. – Juho Sep 26 '15 at 16:49
• 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. – peterh - Reinstate Monica Sep 26 '15 at 19:50