Introduction
Some problems can be solved quickly by computers; others seem to need astronomically long time. Complexity classes (P, NP, NP-hard, NP-complete) are the vocabulary computer scientists use to sort problems by how hard they are to solve. AI search algorithms are the standard techniques an intelligent agent uses to explore a space of possibilities — from finding a route on a map to choosing the best move in chess.
Both topics are favourite sources of BCS, Bank IT-officer and university-admission MCQs. Examiners love one-line facts such as "TSP is an example of an NP-complete problem", "A uses f = g + h"*, and "alpha-beta pruning speeds up minimax". This lesson builds every idea from first principles so that you can answer both the memory-style MCQs and the reasoning-style questions.
Learning objectives
- Define P, NP, NP-hard, NP-complete and draw their relationship diagram.
- Distinguish decision vs optimization problems and tractable vs intractable problems.
- Explain polynomial-time (Karp) reduction and why it proves NP-completeness.
- Give standard examples: TSP, SAT, Knapsack, Vertex Cover.
- Separate approximation algorithms from heuristics.
- Trace uninformed search: BFS, DFS, Uniform-Cost, Iterative Deepening.
- Trace informed search: Greedy Best-First and A* with f = g + h, and state admissibility/optimality.
- Explain hill climbing (local maxima, plateau) and simulated annealing.
- Run minimax and alpha-beta pruning on a worked game tree.
- Describe genetic algorithms (selection, crossover, mutation) and constraint satisfaction (CSP).