7. Limits to Computation (Part 1)¶

Introduction ¹¶

Problem spaces consist of:
- P: Problems that can be solved in polynomial time.
- NP:
  - Problems that can be verified in polynomial time.
  - Sometimes can be solved in polynomial time.
  - They prove that the answer is “YES”.
  - Non-deterministic Problems: they could give different results each time they are run with the same input.
  - They MIGHT or COULD be solved in polynomial time it doesn’t imply or ensure that they will be.
- NP-Hard:
  - Problems that are at least as hard as the hardest problems in NP.
  - No one has been able to solve them in polynomial time.
  - They can not be converted into a Turing machine.
- NP-Complete:
  - Problems that are both in NP and NP-Hard.
- Co-NP:
  - Problems that can be verified do not have a solution in polynomial time.
  - They prove that the answer is “NO”.
Reduction is simply a way of taking one problem and attempting to solve it with another known algorithm.
Using the Turing machine to determine the ‘computability’ of any kind of problem is an example of a reduction.

A reduction is an approach that allows us to solve one problem in terms of another.
Example: asymptotic analysis:
- If we know the asymptotic complexity of one problem but not another, the ability to redefine the problem in terms of the complexity known for another gives us the asymptotic complexity of the problem.
Example: Pairing two list of integers:
- Two sets of integers are given, and we need to pair the smallest from with the smallest from the second set, and so on.
- The problems is so complex on its own; however, we can reduce it to the sorting problem.
- We can sort the two lists separately and then the pairing process becomes easy.

A ‘hard’ problem is one that is expensive in terms of running time with even the best algorithms.
Example: Knapsack problem with brute force solution.

NP completeness or the theory of NP completeness is an approach to ‘hard’ problems.
No fast solution to NP-complete problems is known.
The time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows.
It is important to spot NP-complete problems so that we don’t waste time trying to solve them with algorithms that are not efficient.
One approach that is taken to come up with a solution to NP-complete problems is to use techniques of approximation.

Efficient problem is a problem with running time of O(n^c) for some constant c, where n is the size of the input and c is a constant. O(n^c) is polynomial time.
O(2^n) is exponential time, and it is not efficient.
O(n!) is factorial time, and it is not efficient.
Example: Circuit satisfiability problem:
- Given a circuit with n inputs and a boolean function f that is computed by the circuit, is there an assignment of the inputs that makes the output of the circuit 1?
- The brute force solution is to try all possible assignments of the inputs, which is O(2^n).
- The problem is NP-hard because no one has been able to solve it in polynomial time.
A decision problem is a problem whose output is a single boolean value: YES or NO.
Three classes of decision problems:
- P: Problems that can be solved in polynomial time.
- NP: Problems that can be verified in polynomial time where the answer is YES.
- Co-NP: Problems that can be verified in polynomial time where the answer is NO.

Learning Guide Unit 7: Introduction | Home. (2025). Uopeople.edu. https://my.uopeople.edu/mod/book/view.php?id=453937&chapterid=554133 ↩
Read “lecture 21: NP-Hard Problems”, sections 21.1 through 21.3. Download the pdf. https://my.uopeople.edu/pluginfile.php/1951208/mod_book/chapter/554130/Jeff_nphardRA7-2.pdf ↩
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 ↩
16: Complexity: P, NP, NP-completeness, Reductions (2025). Youtube.com. https://www.youtube.com/watch?v=mr1FMrwi6Ew ↩