12
Computational Complexity
Introduction
It is already discussed that decidable problems have algorithms. For solving a decidable problem, there may be more than one algorithm. The algorithms may differ in time taken and/or memory required to execute and produce the result, for the same input. This is known as computational complexity. It concerns with the question ‘which is the efficient algorithm for solving a decision problem.’ While discussing computational complexity, some underlying particulars such as hardware, software, and data structure are generally ignored. Computer science deals with the theoretical foundations of information, computation, and practical techniques for implementation and application. In this chapter, we shall discuss ...
Get Introduction to Automata Theory, Formal Languages and Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
