Across
- 4. A term used to describe a problem that can’t be solved efficiently on a computer.
- 5. A problem for which no polynomial time algorithm is known and has not been proven to be NP-Complete.
- 7. A term used to describe a problem for which it is impossible to construct an algorithm that always leads to a correct yes-or-no answer.
- 8. A simple hypothetical model of a computing machine that is as capable as any machine available today.
- 11. Order of growth of problems that can be solved efficiently.
- 13. If any of these problems has a polynomial time solution, then all search problems have polynomial time solutions.
Down
- 1. The ability of a computing machine to simulate any other computing machine.
- 2. Order of growth of problems that can not be solved efficiently.
- 3. Proved 21 important problems to be NP-complete.
- 6. The process through which a problem can be solved by converting it into an instance of another problem.
- 9. Proved the first NP-complete problem.
- 10. The first problem proven to be NP-Complete.
- 12. The class of all problems that are checkable in polynomial time.