difference between tractable and intractable problems in algorithms
Answers
Answered by
5
Examples of intractable problems (ones that have been proven to have no
polynomial-time algorithm).
– Some of them require a non-polynomial amount of output, so they clearly will
take a non-polynomial amount of time, e.g.:
∗ Towers of Hanoi: we can prove that any algorithm that solves this problem
must have a worst-case running time that is at least 2n − 1.
∗ List all permutations (all possible orderings) of n numbers.
– Others have polynomial amounts of output, but still cannot be solved in poly-
nomial time:
∗ For an n × n draughts board with an arrangement of pieces, determine
whether there is a winning strategy for White (i.e. a sequence of moves so
that, no matter what Black does, White is guaranteed to win). We can
prove that any algorithm that solves this problem must have a worst-case
running time that is at least 2n.
Examples of tractable problems (ones with known polynomial-time algo-
rithms):
– Searching an unordered list
– Searching an ordered list
– Sorting a list
– Multiplication of integers (even though there’s a gap)
– Finding a minimum spanning tree in a graph (even though there’s a gap)
polynomial-time algorithm).
– Some of them require a non-polynomial amount of output, so they clearly will
take a non-polynomial amount of time, e.g.:
∗ Towers of Hanoi: we can prove that any algorithm that solves this problem
must have a worst-case running time that is at least 2n − 1.
∗ List all permutations (all possible orderings) of n numbers.
– Others have polynomial amounts of output, but still cannot be solved in poly-
nomial time:
∗ For an n × n draughts board with an arrangement of pieces, determine
whether there is a winning strategy for White (i.e. a sequence of moves so
that, no matter what Black does, White is guaranteed to win). We can
prove that any algorithm that solves this problem must have a worst-case
running time that is at least 2n.
Examples of tractable problems (ones with known polynomial-time algo-
rithms):
– Searching an unordered list
– Searching an ordered list
– Sorting a list
– Multiplication of integers (even though there’s a gap)
– Finding a minimum spanning tree in a graph (even though there’s a gap)
Similar questions