Preview lessons, content and tests

Computer Science & Programming solved. All in one platform.

1. To trial the platform and take tests, please take a few seconds to SIGN UP and SET UP FREE.
2. Searching for something specific? See our text overview of all tests. Includes 'real teacher' use videos.

Limits of Computation

The limits of computation are governed by a number of different factors. In particular, there are several physical and practical limits to the amount of computation or data storage that can be performed with a given amount of mass, volume, or energy.

Suggested Video

Types of Problems and Context

There exists two types of algorithms - tractable and intractable. A tractable problem can be solved within a useful period of time. Tractable problems have a polynomial or less time solution. Intractable problems are theoretically solvable (i.e. there exists a corresponding algorithm) but are classified as ‘insoluble’ due to limits of computations - due to the speed of today’s technology, it may take millions of years to solve. Intractable problems do not have a polynomial (or less) time solution.

They cannot be solved within a useful period of time. For these types of problems, we may use a heuristic method. These are approximate solutions to a problem; they are not optimal, but are more useful than their intractable equivalent.

Additional Reading

https://en.wikipedia.org/wiki/Limits_of_computation

Be Inspired - when Algorithms fail - AI and Algos

www.teachyourselfpython.com