Theory of Computation20765 marksIntractability
What do you mean by tractable and Intractable problems? Explain with reference to TM.
What do you mean by tractable and Intractable problems? Explain with reference to TM. [5]
A problem is said to be tractable if it can be solved within reasonable time and space constraints. More formally, a problem is tractable if there exists an algorithm whose complexity (time and space) grows no more rapidly than a polynomial function of the input size n. - An algorithm satisfying ...