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.

Join 30000+ teachers and students using TTIO.

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