skip to content

A routing capacity check certifies yes with a flow and no with a cut — what does being certifiable both ways say about its difficulty?

level: seniorimportance: should knowfreq 40%

answer

  1. look at what the no answer offers
  2. a witness on each side
  3. duality supplies the second certificate
  4. membership in both directions at once
  5. completeness here would collapse two classes

basics

~20 s

It places the problem in NP and co-NP at once. That two-sided certifiability is strong evidence the problem is not among the hardest in NP, because a complete problem sitting in co-NP would force the two classes to coincide — and such problems often turn out to be polynomial-time solvable.

solid answer

~40 s

Certificates in both directions put the problem in **NP intersect co-NP**. A flow respecting capacities and conservation, of value at least k, settles the yes side; a cut separating source from sink whose capacity is below k settles the no side, and the max-flow min-cut theorem guarantees one of the two always exists. That is unusual and informative. Every polynomial-time-solvable problem is in this intersection, and a problem landing there is taken as evidence it is **not NP-complete**: if any NP-complete problem were in co-NP, all of NP would follow it and NP would equal co-NP. Historically the pattern has paid out — the decision form of linear programming was known to be certifiable both ways, via duality, well before a polynomial-time algorithm for it was found.

code

pseudocode · 11 lines
pseudocode
function check_capacity_certificate(network, k, certificate):
    if certificate.kind == FLOW:
        if not respects_capacities(certificate): return REJECT
        if not conserves_at_every_internal_node(certificate): return REJECT
        if value(certificate) >= k: return ACCEPT_YES
        return REJECT
    if certificate.kind == CUT:
        if not separates_source_from_sink(certificate): return REJECT
        if capacity_across(certificate) < k: return ACCEPT_NO
        return REJECT
    return REJECT

go deeper

for a junior

Recall which object supports which verdict: a routing plan shows the capacity is achievable, while a bottleneck separating the endpoints shows it is not. Both are checkable without redoing the search.

for a middle

Explain why the two certificates are exhaustive — the largest flow value equals the smallest cut capacity — and name the class that having both places the problem in.

for a senior

Use it as a design question: when your system must justify a negative verdict to someone who disputes it, look for a dual object to hand over rather than an appeal to your own run.

for a principal

Treat dual certifiability as a property worth buying. Choosing a formulation that has a dual changes what your platform can prove to auditors and partners, independently of how fast the solver happens to be.

## Two certificates, one problem Most interesting problems are lopsided: one verdict is easy to demonstrate and the other is not. A **dually certified** problem is the exception, where a short checkable object exists whichever way the answer falls. The capacity question is the standard illustration. Take a network with capacities on its edges, a source, a sink, and a threshold `k`. The question is whether `k` units can be routed simultaneously. - **Yes** is certified by a **flow**: an assignment of a rate to every edge that never exceeds the edge's capacity and conserves rate at every intermediate node. A checker verifies both properties edge by edge and node by node, then reads off the value. If the value is at least `k`, the answer is yes and the checker has proved it. - **No** is certified by a **cut**: a split of the nodes with the source on one side and the sink on the other. A checker sums the capacities of the edges crossing forward across the split. If that total is below `k`, no routing can carry `k` units, because everything that reaches the sink must cross. The **max-flow min-cut theorem** is what makes the pair exhaustive: the largest achievable flow value equals the smallest cut capacity. So for any instance, one of the two certificates exists, and neither checker ever searches. ## Duality is the general mechanism The flow-cut pair is one instance of a broader pattern. In **linear-programming duality**, every maximisation problem has a partner minimisation problem, and any feasible solution of the partner bounds the original from the other side. That gives the same two-sided structure: - A feasible point of the original certifies 'this objective value is achievable'. - A feasible point of the dual certifies 'nothing beats this value'. - When the two objectives meet, the pair together certifies optimality with no search left to do. - When the original has no feasible point at all, an infeasibility certificate in the dual proves it — a derived contradiction that a checker replays. This is why 'is there a dual object?' is a productive question to ask of any problem where the negative verdict matters to you. ## What the intersection predicts | Position | What it means | Certificates | |---|---|---| | In NP only | yes answers are demonstrable | one direction | | In co-NP only | no answers are demonstrable | one direction, flipped | | In NP and co-NP | both verdicts are demonstrable | both directions | | In P | both verdicts are computable directly | rerun the decision procedure | Two consequences are worth carrying: 1. **P sits inside the intersection.** If you can decide the question outright in polynomial time, you need no certificate in either direction, so the membership is free. The intersection is therefore not exotic — it contains everything easy. 2. **An NP-complete problem in the intersection would collapse the classes.** Suppose some NP-complete problem also lay in co-NP. Every problem in NP reduces to it, and co-NP is closed under those reductions, so all of NP would land in co-NP, and complementing gives the reverse inclusion. NP would equal co-NP — widely doubted. So a dually certified problem is, by the standard reasoning, **unlikely to be NP-complete**. ## The trap: two-sided does not mean easy Membership in the intersection is a statement about certificates, not about algorithms. It says a checker exists for each verdict; it says nothing about how to find the certificate. Problems are believed to sit in the intersection without being known to lie in P, and the belief has survived decades of attention. The honest summary is a ranking of confidence, not a proof: - **Proven**: if both certificates exist for every instance, the problem is in NP intersect co-NP. - **Proven**: everything in P is in that intersection. - **Conditional**: the problem is not NP-complete *unless* NP equals co-NP. - **Not implied**: that a polynomial-time algorithm exists, even though history shows several such problems eventually got one. ## How to use this at work When a checker must report a negative verdict that someone will act on — a capacity plan rejected, a placement declared impossible — ask what object you can hand the person who disputes it. If the problem has a dual, the answer is a cut, a bound, a derived contradiction, and the dispute ends with a re-check rather than an argument about your implementation. If it has no dual, that absence is itself the finding, and the honest report says which verdict your system can prove and which it can only assert.

  • Does membership in NP intersect co-NP prove the problem is in P?
    No. P is contained in the intersection, but the containment is not known to be tight, and problems are believed to sit in the intersection without any polynomial-time algorithm. Two-sided certifiability is about what a checker can verify when handed an object, not about how expensive it is to produce that object.
  • What exactly breaks if an NP-complete problem turns out to be in co-NP?
    Every problem in NP reduces to it in polynomial time, and co-NP is closed under such reductions, so all of NP lands in co-NP. Complementing both sides gives co-NP inside NP as well, so the classes coincide. That single membership would settle an open question, which is why it is treated as strong evidence against.

saying these in an interview costs you the question

  • Says a problem with certificates on both sides must be solvable in polynomial time.
  • Treats the intersection as exotic, forgetting every polynomial-time problem lives there.
  • Reverses the pair: claims a cut certifies the yes answer and a flow the no answer.
  • Assumes NP-complete problems carry certificates for their no answers too.
  • Concludes from two-sided certificates that finding a certificate is also cheap.