HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What are the definitions for "hard problem" and "easy problem"?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemthewhatarehardeasyforanddefinitions

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?

Solution

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".

Context

StackExchange Computer Science Q#47578, answer score: 9

Revisions (0)

No revisions yet.