Introduction to Time Complexity – What Are P Problems?

中文 | English

• Introduction to Time Complexity – What Are P Problems?

  • Basic Concepts in Computational Complexity

    • Why do we emphasize poly-time?

  • P Problems

  • Pseudo-Polynomial Time

  • Weakly Polynomial Time

  • Strongly Polynomial Time

  • Final Comparison Table

Basic Concepts in Computational Complexity

Before we dive into NP, NP-completeness, and polynomial reductions, we first need a shared language:

What is “algorithmic complexity”? What is “polynomial time”? Why are some algorithms fast but not poly-time?

We begin with three foundational complexity notions:

• Polynomial Time

• Pseudo-Polynomial Time

• Weakly Polynomial Time

These concepts will appear repeatedly later.

Why do we emphasize poly-time?

In theoretical CS, poly-time is universally considered the threshold of efficient computation.

Because:

1. The growth of polynomial-time algorithms (e.g., $n$$n$, $\begin{array}{c}n\\ logn\end{array}$$n \\log n$, $n^2$$n^2$, $n^3$$n^3$) is controlled.

2. Changing computers, languages, and constant factors will not change its complexity class.

3. Poly-time problems are scalable in real engineering.

Examples:

Thus, P problems (Polynomial-Time Problems) refer to problems solvable within practical running time.

P Problems

A problem belongs to P if there exists an algorithm whose running time is:

$O(n^k)$$O(n^k)$

for some constant $k$$k$.

Classic poly-time algorithm examples

1. Dijkstra Shortest Path (Non-negative weights)

• Code: Graph.hpp

• Running time:

  • $O(m\log n)$$O(m \log n)$ or

  • $O(n^2)$$O(n^2)$

• Therefore, Shortest Path is a classic P problem.

2. Maximum Flow

• Notes: Network Flow

Thus, Max Flow is also a P problem.

3. Minimum Spanning Tree (MST)

• Code: Graph.hpp

• Kruskal / Prim run in: $O(m\log n)$$O(m \log n)$

Hence MST is also a P problem.

These algorithms form the foundation of tractable computation.

Pseudo-Polynomial Time

One-sentence definition:

A pseudo-polynomial algorithm depends on the numerical value $V$$V$ of the input, not its bit-length $\log V$$\log V$.

The best example comes from dynamic programming.

Classic Example: 0/1 Knapsack DP

(570 course notes: DP Part 1)
(Carl’s tutorial: 01 Knapsack)

DP complexity:

$O(nW)$$O(nW)$

Where:

• $n$$n$ = number of items

• $W$$W$ = knapsack capacity (numeric value)

Why is it not polynomial?

Because $W={10}^9$$W = 10^9$ only needs 30 bits to represent—but the DP must run one billion steps.

Thus it is not poly-time.

A more intuitive explanation

You asked:

Different Paths DP is poly-time, but Knapsack DP is not. Why?

My explanation:

• For grid DP (e.g., “Unique Paths”), the size of the DP table grows with the input size (the grid).

• For Knapsack, the DP table height grows with the numeric value W, not with input size.
  A single digit change in W (e.g., W+1) adds another entire DP row.

This disconnect between “input length” and “DP table size” makes it pseudo-poly.

Example table

Pseudo-poly algorithms frequently appear in NP-hard optimization:

• Knapsack

• Subset Sum

We'll revisit this when discussing NP-hardness.

Weakly Polynomial Time

A weakly polynomial algorithm lies between true polynomial and pseudo-polynomial.

One-sentence definition:

Weakly polynomial time = polynomial in $n$$n$ and bit-length $\begin{array}{c}\\ logV\end{array}$$\\log V$, but not in $V$$V$ itself.

Thus:

• weak-poly ⇒ in P

• pseudo-poly ⇒ not necessarily in P

Classic example: Linear Programming (LP)

LP solvers (ellipsoid / interior-point) run in: $\mathrm{poly}(n,B)$$\operatorname{poly}(n, B)$

Where:

• $n$$n$ = number of variables/constraints

• $B$$B$ = bit-length of input coefficients

This is truly polynomial-time and far better than pseudo-poly.

Strongly Polynomial Time

Definition:

$\mathrm{poly}(n)$$\operatorname{poly}(n)$

Only depends on structural input size.

Examples:

• BFS / DFS

• Prim / Kruskal

• Hopcroft–Karp matching

• Some max-flow algorithms (e.g., Orlin)

Strongly poly-time algorithms are the most robust.

Final Comparison Table