86.6k views
1 vote
What are tractable, intractable, unsolvable, and decision problems in computer science?

User Tvo
by
7.5k points

1 Answer

6 votes

Final answer:

Tractable problems can be solved efficiently, intractable problems lack efficient solutions, and unsolvable problems cannot be solved by any algorithm. Decision problems have yes/no answers.

Step-by-step explanation:

The terms tractable, intractable, unsolvable, and decision problems are common in computer science, particularly in the context of problem-solving and algorithm development. A tractable problem is one that can be solved by a computer algorithm in a reasonable amount of time, typically polynomial time. Conversely, intractable problems are those for which no efficient solution is known, and they often require non-polynomial time to solve. An unsolvable problem is one for which no algorithm can be created that will always lead to a solution. Finally, a decision problem is a question with a yes or no answer, often related to the properties of computational models.

An algorithm is a set of well-defined instructions for solving a problem, whereas a heuristic is a practical approach that does not guarantee an optimal solution but is useful for making efficient, quick decisions. Some common roadblocks to effective problem solving and decision making include lack of clarity, incomplete information, and cognitive biases like overconfidence or anchoring.

User Pbaylis
by
7.3k points