Normal people are often confused by the vocabulary of computer scientists because we tend to use common words in very specific and precise ways. Some of the most frequent misunderstandings between computer scientists and others occur when discussing the concept of "difficulty" and how "hard" some task will be to accomplish. Below are some common terms, along with what they mean to computer scientists. You'll note that non-computer-scientists will often understand these terms entirely differently (and with less precision).

Cheap solution: A solution to a problem that will not take very long or cost very much to implement. Cheap solutions to non-trivial problems are often very difficult to think of. Some problems do not have any cheap solutions.

Expensive solution: A solution to a problem that will cost a lot of time or money to implement. Expensive solutions are often very easy to think of, but there are many degrees of expensiveness. Some solutions are so expensive that they are infeasible to implement, even if they're trivial to conceptualize.

Trivial Problems: Problems that are trivial have known solutions and are therefore inherently uninteresting. They've been solved before, and there's no doubt that a previous solution will be able to satisfy the current need. Ironically -- and contrary to common usage -- trivial solutions to a problem are often the most expensive and time-consuming; it's simple to solve a problem with brute-force. Some problems are themselves trivial, and every reasonable solution is uninteresting even if expensive. Examples of trivial problems: performing arithmetic, algebra, or calculus calculations; building a house; sweeping a sidewalk; writing a side-scrolling adventure game.

Easy Problems: Easy problems are those that are quite similar to trivial problems, but that will require known solutions to be tweaked and modified. There's a very high probability that a known solution can be successfully adapted to this new problem, but there are uncertainties that cannot be completely accounted for at the start. As with solutions to trivial problems, solutions to easy problems might still be very expensive to implemented. Examples of easy problems: applying existing artificial intelligence techniques to a new purpose; building a unique skyscraper in an unusual location; figuring out which mathematical formulas to apply to a particular problem.

Hard Problems: Hard problems have no known solutions, but are considered to be within the realm of possibility. There may be similar problems with known solutions that lead the scientist to believe that the hard problem under consideration can also be solved, but this is intuition, not certainty. Upon investigation, hard problems generally turn out to be either easy or impossible, but until some research is done you can't be sure. If a solution is found, it may be either cheap or expensive to implement, and this cost is often independent of how hard the solution was to find. Most people never encounter hard problems during the normal course of their lives. Examples of hard problems: deciding whether or not P=NP; analyzing the emergent effects of a complex adaptive system; building a skyscraper on Mars.

Impossible Problems: These problems have no solutions. It's important to note that impossible problems are not merely expensive to solve, they cannot be solved without a fundamental change to the laws of the universe or a complete revolution in our understanding of science. Sometimes problems are mistakenly categorized as impossible when they're actually not, and when a solution to a formerly-thought-to-be-impossible problem is discovered it is a very significant event. Impossible problems are generally considered to be a waste of time to pursue... but then breakthroughs are made occasionally. Many impossible problems are actually easy problems with impossible restrictions. Examples of impossible problems: finding the optimal route for a traveling salesman in less than exponential time; building a faster-than-light spaceship; finding the largest prime number.

0 TrackBacks

Listed below are links to blogs that reference this entry: The Vocabulary of "Difficulty" In Computer Science.

TrackBack URL for this entry:



Email blogmasterofnoneATgmailDOTcom for text link and key word rates.

Site Info