Optimization Problems & P vs NP — Computer Science

Definition

An optimization problem asks for the best solution among all feasible solutions, according to some objective function to be minimized or maximized — as opposed to a decision problem, which only asks a yes/no question (e.g., "does a path of length ≤ k exist?" is a decision problem; "what is the shortest path?" is the corresponding optimization problem).

The Two General Categories

Minimization problems — find the feasible solution that minimizes the objective function. Examples: shortest path, minimum spanning tree, minimum-cost assignment.
Maximization problems — find the feasible solution that maximizes the objective function. Examples: maximum flow, 0/1 knapsack (maximize value), longest increasing subsequence.

Standard Mathematical Representation

Given a set of feasible solutions (the search space) $S$ and an objective function $f : S \to \mathbb{R}$ :

\text{Minimize (or Maximize) } f(x) \quad \text{subject to } x \in S

where $S$ is typically defined by a set of constraints, e.g. $g_i(x) \leq 0$ for $i = 1, \dots, m$ . An optimal solution $x^*$ satisfies (for a minimization problem):

f(x^*) \leq f(x) \quad \text{for all } x \in S

P, NP, NP-Complete, and NP-Hard

Class	Meaning
P	Problems solvable in polynomial time by a deterministic algorithm
NP	Problems verifiable in polynomial time — given a proposed solution (a "certificate"), you can check its correctness quickly, even if finding it might be hard
NP-Complete	The hardest problems within NP — in NP, AND every other NP problem can be reduced to it in polynomial time (e.g., Boolean Satisfiability, Hamiltonian Path, Traveling Salesman decision version)
NP-Hard	At least as hard as the NP-Complete problems, but may not itself be in NP (e.g., the optimization — not decision — version of an NP-Complete problem)

$P \subseteq NP$ always holds (anything solvable quickly can also be verified quickly, trivially, by just solving it) — the open question is whether that inclusion is strict.

Is P = NP?

This is one of the seven Clay Mathematics Institute Millennium Prize Problems and remains unsolved — no one has proven P = NP, and no one has proven P ≠ NP. Most computer scientists conjecture P ≠ NP (i.e., that there genuinely exist problems that are easy to verify but hard to solve from scratch), but this remains unproven.

Why it matters: if P were proven equal to NP, every problem whose solution can be quickly checked could also be quickly found — with sweeping implications across cryptography (most of which relies on certain problems being hard to solve, easy to verify), optimization, and computer science generally. Because no proof exists either way, algorithm designers treat NP-Complete/NP-Hard problems as practically intractable at scale and reach for heuristics/approximations instead of insisting on an exact polynomial-time solution.

Why Optimization Problems Are Often NP-Hard

The optimization version of an NP-Complete decision problem is typically NP-hard. Classic example: for the Traveling Salesman Problem, "does a tour of length ≤ k exist?" is NP-Complete (in NP: given a tour, checking its length ≤ k is fast), while "what is the shortest possible tour?" is NP-hard (there's no way to quickly verify a proposed tour actually IS the shortest one, without essentially re-solving the problem). This is exactly why optimization problems so often land in the NP-hard bucket even when their yes/no counterpart is merely NP-Complete.

Since an exact algorithm for an NP-hard problem requires (conjectured) exponential worst-case time, real applications fall back on heuristic/approximation methods — greedy algorithms, local search, simulated annealing, genetic algorithms, branch-and-bound with pruning — trading a guaranteed-optimal answer for a fast, good-enough one. See the Heuristic Search & Genetic Algorithms page for the full discussion of when this trade-off is appropriate.

Exam Angle

Pair this page directly with the Graphs page's "Shortest Path vs Longest Path" question (shortest path is solvable in polynomial time via Dijkstra; longest simple path is NP-hard) — it's the same P-vs-NP-hard distinction applied to a concrete graph example.

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Exam Practice: Defining Optimization Problems

2023, Paper I, Q8(c) (6 marks) — What is an Optimization problem? What are its 2 general categories? Write down mathematical representation of a standard optimization problem.

Model answer: see the Definition, "The Two General Categories," and "Standard Mathematical Representation" sections above — state the minimize/maximize form explicitly with the constraint set $S$ , and name both minimization (shortest path, MST) and maximization (max flow, knapsack) with one example each.

📝 Exam Practice: The P vs NP Question

2020, Paper I, Q8(a) (4 marks) — Is P = NP? Comment.

Model answer: No proof exists either way — this is an open Millennium Prize Problem. The general belief among computer scientists is P ≠ NP (some problems are inherently easy to verify but hard to solve), but this is a conjecture, not a theorem. A strong answer states: (1) the definitions of P and NP, (2) that $P \subseteq NP$ is proven but the reverse inclusion is not resolved, (3) the practical stance taken in algorithm design — treat NP-hard/NP-complete problems as intractable at scale and use heuristics — regardless of the theoretical answer.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2020 · Paper-I · Q8(a) · 4 marks

Q. Is P = NP? Comment.

Ans.

P is the class of problems solvable in polynomial time. NP is the class of problems whose solutions can be verified in polynomial time. Every problem in P is also in NP.
The question: can every problem whose solution is quickly checkable also be quickly solved? This is the biggest open problem in computer science (a Clay Millennium Prize problem).
NP-complete problems (such as travelling salesman and Boolean satisfiability) are the hardest in NP. A fast algorithm for one would solve all of them.
Belief: most experts think P ≠ NP, but it has not been proved. If P = NP, much of modern cryptography would be broken.

2020 · Paper-I · Q6(a)(b) · 10 marks

See Graphs for the longest-path algorithm and its classification (exponential, NP-hard) versus shortest path (P).

2023 · Paper-I · Q8(c) · 6 marks

Q. What is an optimization problem? What are its two general categories? Write the mathematical representation of a standard optimization problem.

Ans.

An optimization problem asks for the best solution (the minimum or maximum of an objective) among all feasible solutions.
Two general categories:
- Continuous optimization: variables take real values (for example linear and non-linear programming).
- Discrete (combinatorial) optimization: variables come from a finite or countable set (for example travelling salesman, knapsack, shortest path).
Standard form:

Minimize f(x) subject to gᵢ(x) ≤ 0 for i = 1…m, hⱼ(x) = 0 for j = 1…p, and x ∈ X.
f is the objective function, and gᵢ and hⱼ are the constraints. A maximization problem is turned into minimization with −f(x).