COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Unreasonable time algorithms can never be ran and will never produce a correct solution
|
|
|
Undecidable problems are a type of problem for which it has been proven that there simply is no algorithm that will always produce a correct result
|
|
|
Unreasonable problems grow in size so quickly, even for small inputs, that it is usually unreasonable to run that algorithm
|
|
|
With regards to undecidable problems, the issue isn’t simply that it takes a long time, but that it is demonstrably impossible to write such an algorithm.
|
Detailed explanation-1: -Explanation: Problems cannot be solved by any algorithm are called undecidable problems. Problems that can be solved in polynomial time are called Tractable problems.
Detailed explanation-2: -An unsolvable problem is one for which no algorithm can ever be written to find the solution. An undecidable problem is one for which no algorithm can ever be written that will always give a correct true/false decision for every input value.
Detailed explanation-3: -Unreasonable Time: If the number of steps is an exponential function of the size of the input (or another function larger than any polynomial), we say that the algorithm takes an unreasonable amount of time. For an algorithm that takes 2n time, just adding 1 to the input size (n) doubles the number of steps!