---
title: "Living with NP-Hardness: Approximation and Heuristics"
description: "Hardness rules out an exact fast method for every input, not a useful answer. An approximation algorithm carries a proved ratio to the optimum, while a heuristic carries no promise and has to be judge"
canonical: https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u
source: https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Living with NP-Hardness: Approximation and Heuristics

Hardness rules out an exact fast method for every input, not a useful answer. An approximation algorithm carries a proved ratio to the optimum, while a heuristic carries no promise and has to be judged by measurement.

Subject: Computing · Area: Algorithms & Data Structures · Ages 21 to 22
Page: https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u

## Ready when they can

- Run a 2-approximation for vertex cover and argue the factor from the matching it builds
- Distinguish an approximation with a proved ratio from a heuristic without one
- Choose between exact, approximate and heuristic for a stated deadline and input size

## Lesson: Good Answers Without Perfect Ones

When a problem is NP-hard, no exact method runs fast on every input. That rules out perfection, not usefulness. You still have three doors: an exact method for small inputs, an approximation with a proved ratio, or a heuristic you judge by measurement. This lesson teaches you to pick the right door.

**Example.** For vertex cover, build a matching: a set of edges that share no vertices. Take both ends of every matched edge into your cover. Every matched edge needs its own vertex in any optimum, so the optimum holds at least one vertex per matched edge. Your cover holds two per matched edge, so it is never larger than twice the optimum. That is a 2-approximation.

An approximation carries a promise that holds on every input, like never worse than twice the optimum. A heuristic carries no promise at all, so you judge it by testing on real inputs. Saying a heuristic usually works well reports measurements. It does not turn the heuristic into an approximation.

**Tip.** Match the method to the deadline and the input size. Small input with time to spare means exact. Huge input with a guarantee required means approximation. Huge input where good enough is fine, and you can test, means heuristic. Name what you are giving up before you start.

**Recap.** Hardness ends exact methods for every input, so promise a ratio with an approximation or measure a heuristic, and pick by deadline and size.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Greedy Choice and the Exchange Argument](https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV-)
- [P, NP and What NP-Complete Means](https://lightmysky.com/learn/computing/p-np-and-what-np-complete-means-mt_wwmNVG_VnB)

## Opens up

- [Randomised Algorithms and the Probabilistic Method](https://lightmysky.com/learn/computing/randomised-algorithms-and-the-probabilistic-method-mt_4ShN_WlT0-)
- [Approximation Ratios and How One Is Proved](https://lightmysky.com/learn/computing/approximation-ratios-and-how-one-is-proved-mt_8pmBztDkFD)