Theory of Computation2080.15 marksIntractability
What is intractability? Define time and space complexity of turing machine.
What is intractability? Define time and space complexity of turing machine. [5]
Intractability is a concept used to classify problems that cannot be solved in polynomial time but instead require exponential time algorithms. - Problems that can be solved within reasonable time and space constraints are called tractable problems. - Problems that cannot be solved in polynomial ...