Skip to content

8. Limits to Computation (Part 2)

Introduction 1

  • The most notable characteristic of NP-complete problems is that no fast solution to them is known; that is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows.
  • As a result, the time required to solve even moderately large versions of many of these problems quickly becomes so great that it isn’t practical to solve them using current technology solutions.
  • Determining whether or not it is even possible to solve these problems quickly is one of the principal unsolved problems in Computer Science today.
  • While a method for computing the solutions to NP-complete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems.
  • It is important for programmers to be able to recognize an NP-complete problem so that they don’t unknowingly waste time trying to solve a problem which so far has eluded generations of computer scientists.
  • In NP-complete problems brute-force approach to finding an optimal solution is not practical so another approach might be to make an educated guess at the best solution and then test it to determine if in fact that it was the correct one using approximations.
  • Impossible problems:
    • Problems that cannot be solved by any algorithm.
    • Examples include the halting problem and the decision problem, or any problem that can not be computed in a finite number of steps.
    • In general, a problem is impossible if it cannot be solved by any algorithm in a finite number of steps; that is, if it includes an infinite loop.
    • The halting problem is a decision problem that can be stated as follows: given a description of an arbitrary computer program and an input, determine whether the program will finish running or continue to run forever.

Ch17: Limits to Computation [^2]

Ch8: NP-Complete Problems 2

Ch9: Coping with NP Completeness 3

References

[^2]‌: Chapter 17: Limits to Computation in A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A. Shaffer.Read “lecture 21: NP-Hard Problems available at http://drona.csa.iisc.ernet.in/~gsat/Course/DAA/lecture_notes/jeff_nphard.pdf

  1. Learning Guide Unit 8: Introduction | Home. (2025). Uopeople.edu. https://my.uopeople.edu/mod/book/view.php?id=453941&chapterid=554140 ↩

  2. Chapter 8 NP Complete Problems in Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani available at http://www.cs.berkeley.edu/~vazirani/algorithms/chap8.pdf ↩

  3. Chapter 9 Coping with NP Completeness in Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani available at http://www.cs.berkeley.edu/~vazirani/algorithms/chap9.pdf ↩