Engineering / Mathematics — Probabilistic Algorithms
Strict Polynomial Time
Strict versus expected polynomial time, and how a Las Vegas algorithm is converted into a bounded-time one.
Executive summary
An algorithm running in expected polynomial time may occasionally run much longer. Strict polynomial time bounds every execution, which some settings require.
The conversion between the two costs an error probability, and Markov's inequality supplies the trade.
Learning objectives
- Distinguish strict from expected polynomial time.
- Convert between the two using truncation.
- Recognise where strictness is required.
01The two notions
Time bounds
Strict polynomial time: there is a polynomial q such that every execution on input of length n halts within q(n) steps, regardless of the coins.
Expected polynomial time: the expected number of steps is bounded by a polynomial, with individual executions possibly longer.
Randomised quicksort and repeat-until-success prime generation are expected polynomial time. Neither has a bound on the worst coin sequence, though the probability of a long run decays rapidly.
02Truncation
Expected to strict
An algorithm with expected running time T, truncated at kT steps, halts within a strict bound and fails to produce an answer with probability at most 1/k, by Markov's inequality.
Truncation converts a Las Vegas algorithm into a Monte Carlo one: bounded time, small failure probability. Repeating the truncated version drives the failure probability down geometrically while keeping every individual run bounded.
Bound the expectation
Establish expected running time T.
Truncate
Halt at kT steps and report failure if incomplete.
Amplify
Restart with fresh randomness; t attempts fail with probability at most k^{−t}.
Total bound
Strict bound ktT with failure probability k^{−t}.
03Where strictness matters
Real-time systems
A deadline must be met on every execution, not on average. An unbounded tail is a correctness failure regardless of its probability.
Side-channel resistance
Data-dependent running time leaks information. Cryptographic implementations require fixed time, which is stronger than strict polynomial time.
Complexity classification
Some complexity classes are defined with strict bounds, so membership arguments require the conversion.
04Frequently asked questions
Is expected polynomial time a weaker guarantee?
Formally weaker, and adequate for most purposes. Tail probabilities decay fast enough that an execution exceeding a modest multiple of the expectation is vanishingly unlikely.
Does truncation always work?
It always produces a bounded-time algorithm, but only helps if failure is detectable and recoverable. Where a partial result cannot be distinguished from a complete one, truncation is not available.
Are the two classes actually different?
For decision problems with two-sided error the distinction largely dissolves, since truncation and amplification convert between them. For zero-error algorithms the distinction is real and the classes differ.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 156-157.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.