A tractable problem is a problem that can actually be solved in practice. Conversely, a problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice any solution takes too many resources to be useful, is an intractable problem. The term infeasible (literally "cannot be done") is sometimes used interchangeably with intractable and likewise, the term Feasible is sometimes used interchangably with Tractable.

The concept is important because a first step to machine learning problem selection is ensuring that the problem can be solved. This involves thinking through the premise and formulation of the problem, including analysis of the available data. To determine the Tractability of a problem, one might ask if sufficient historical data are available, and are there sufficient data signals and labels for an algorithm to be trained successfully? For many supervised learning problems, the number and quality of available labels becomes a key limiting issue.

Posts

Wikitag Contributions

Comments