Semi Hard Problem

A semi-hard problem is a problem which requires a human-noticeable amount of time to solve on a typical computer; but is not intractable. Examples include partial hash collisions, factoring of medium-sized numbers (64-128 bits), etc.

SemiHardProblems are useful in combatting DenialOfService attacks, wherein the amount of requests for service (spam emails, etc) generated by an attacker is far greater than what a legitimate user would generate. Solving one instance of the problem is not a significant load on a legitimate user's system, but solving many different instances of the problem is.

One application of this trick is HashCash.


EditText of this page (last edited February 1, 2006) or FindPage with title or text search