2 of 12

1. Introduction to Problems in Computation

Definition of a Computational Problem:

A computational problem is a task solved using an algorithm, involving input and desired output.

Importance of Understanding Solvable and Unsolvable Problems

Knowing the distinction helps in resource allocation, avoiding futile efforts, and understanding the limits of computation.

3 of 12

2.Solvable Problems

“Problems for which algorithms can provide solutions in a finite amount of time”

Examples of Solvable Problems:

Sorting Algorithms:

Bubble Sort: Simple comparison-based algorithm with a worst-case time complexity of O(n^2).
Quick Sort: Efficient divide-and-conquer algorithm with an average-case time complexity of O(n log n).

Searching Algorithms:

Binary Search: Efficient algorithm for finding an item in a sorted array with a time complexity of O(log n).

4 of 12

Methods to Determine Solvability

Algorithm Design and Analysis:Creating step-by-step procedures to solve problems and analyzing their efficiency.

Computational Complexity: Studying the resources required by algorithms to solve problems, such as time and space.

5 of 12

3.Unsolvable Problems�

Definition and Characteristics:

Problems for which no algorithm can provide a solution for all possible inputs.

Examples of Unsolvable Problems:

-The "Squaring the Circle" problem is a classic example of an unsolvable problem in the realm of geometric constructions.

- The Halting Problem: Determining whether a given program will finish running or continue forever. (use Diagonalization method)

- Turing's Proof of Undecidability: Demonstrates that some problems cannot be solved by any algorithm.

6 of 12

Methods to Identify Unsolvability

Methods to Identify Unsolvability:

Reduction Techniques: Showing that solving one problem would solve another known unsolvable problem.

Diagonalization:A method used in proofs to show that certain problems cannot be computed.

7 of 12

4. Key Concepts and Theorems

- Turing Machines: Abstract machines that can simulate any algorithm's logic.

- Church-Turing Thesis: Hypothesis stating that any function that can be computed algorithmically can be computed by a Turing machine.

- Gödel's Incompleteness Theorems: Theorems demonstrating inherent limitations in formal systems.

8 of 12

5. Implications of Unsolvable Problems�

- Impact on Computer Science and Mathematics:

Influences fields like cryptography, algorithmic information theory, and artificial intelligence.

- Practical Considerations for Software Development:

Recognizing unsolvable problems can save time and resources by preventing attempts to solve the impossible.

9 of 12

6. Case Studies and Examples�

Real-world Scenarios Involving Solvable and Unsolvable Problems:

- Traveling Salesman Problem (TSP): While finding an exact solution is computationally hard, approximation algorithms can provide near-optimal solutions.

- Encryption and Decryption: Many encryption algorithms rely on problems that are believed to be unsolvable within practical time frames.

10 of 12

How to Approach Complex Computational Problems

Techniques like heuristics, approximation, and probabilistic algorithms.

11 of 12

Summary and Conclusion�

Distinguishing between solvable and unsolvable problems helps in understanding computational limits and applying appropriate strategies.

Essential for effective problem-solving and efficient resource use in computation.

1 of 12