skip to content

Your team wants the policy validator to emit a machine-checkable proof that no rule conflict exists — how do you decide whether that is reasonable?

level: principalimportance: should knowfreq 30%

answer

  1. ask which claim is being promised
  2. universal claims need a bounded scope
  3. shrink the language, not the timeout
  4. unknown deserves its own verdict
  5. polynomial fragments are closed under complement

basics

~20 s

Decide by the shape of the claim, not the budget. A proof of absence is a universal claim, complete for co-NP while conditions stay expressive. Either restrict the condition language until the claim lands in a class closed under complement, or ship a third verdict: unknown.

solid answer

~50 s

Start by naming what is being promised. 'No conflict exists' quantifies over every request the schema allows, which is a co-NP claim and, for an expressive condition language, as hard as anything in that class. Three responses are honest, and only one of them changes the difficulty. **Restrict the language** — if conditions are limited to a fragment where pairwise compatibility is decidable directly, the problem falls into P, which is closed under complement, and both verdicts become certifiable by rerunning the check. **Restrict the scope** — certify absence over a declared finite attribute domain or within one rule group, and say so in the verdict. **Report three outcomes** — conflict with a witness, conflict-free within a stated fragment, or unknown with the budget that was exhausted. What is not honest is folding `unknown` into `conflict-free`, and no amount of extra compute moves the claim out of the class it lives in.

go deeper

for a junior

Recall the difference between a result and a guarantee: a check that finished without finding anything is not the same statement as 'this cannot happen for any input'.

for a middle

Explain why the absence claim quantifies over the whole request space, and what restricting the condition language does to that quantifier.

for a senior

Design the verdict vocabulary: three outcomes rather than two, a certificate attached to every positive finding, and an explicit statement of what was quantified over.

for a principal

Own the tradeoff between an expressive rule language and a provable guarantee, decide it by who consumes the verdict and what they gate on it, and refuse the option where a timeout silently stands in for a proof.

## What the requirement actually asks for A machine-checkable proof of absence is a specific object: something short that a sceptic replays in polynomial time and comes away convinced no request anywhere triggers two opposing rules. The positive verdict already has such an object — two rule ids and one request. The requirement asks for the mirror, and the mirror is a **universal** claim: for all requests, no opposing pair fires. With conditions written as arbitrary boolean formulas over attributes, that claim is complete for co-NP. Nobody knows a short certificate for a co-NP-complete claim, and finding one for this instance family would settle an open question. So the decision is not about effort. It is about which promise the system makes. ## Four responses, ranked by what they change 1. **Restrict the condition language.** The only response that changes the *class*. If conditions are limited to, say, conjunctions of attribute-equals-value tests, two rules can fire together exactly when no attribute is bound to two different values, which is decided per attribute per pair. The whole check becomes polynomial in the number of rules and attributes. P is closed under complement, so both verdicts become certifiable. 2. **Restrict the scope of the claim.** Keep the language and shrink what is quantified over: certify absence within one rule group, or over an attribute domain declared finite and small enough to enumerate. The verdict is still universal, but over a range you can state and defend. 3. **Change the verdict vocabulary.** Report three outcomes rather than two. `Conflict`, with a witness attached. `Conflict-free`, only where option 1 or 2 licenses it. `Unknown`, with the exhausted budget named. This changes nothing about difficulty and everything about honesty. 4. **Invert the product.** Publish only what you can prove: every conflict found, each with its certificate, and no absence claim at all. Weaker, and sometimes exactly right for a review workflow where finding real conflicts is the value. ## What changes and what does not | Move | Class of the absence claim | Certificate for absence | What you give up | |---|---|---|---| | Nothing; expressive conditions | co-NP-complete | none known in general | the guarantee itself | | Restrict the condition language | P | rerun the decision procedure | expressiveness for rule authors | | Restrict the quantified scope | depends on the scope | an enumeration you can bound | coverage, which must be stated | | Add compute or a longer timeout | unchanged | none | nothing gained on the claim | The fourth row is the one leadership usually needs to hear. Worst-case hardness is a property of the problem family, not of your hardware allocation, and doubling the budget does not convert a search into a proof. ## Writing the contract The wording of the verdict is where this lands in production, and it deserves the same care as an interface: - Say which **fragment** of the condition language the conflict-free verdict is licensed for, and fail loudly when a rule leaves that fragment rather than silently downgrading. - Attach the **certificate** to every positive finding, so a disputed conflict is re-checked instead of re-argued. - Make `unknown` a first-class verdict with its own downstream handling. A consumer that treats `unknown` and `conflict-free` identically has quietly re-introduced the promise you refused to make. - Record what was quantified over. 'No conflict among rules in group A over the declared attribute domain' is a sentence someone can act on; 'no conflicts found' is not. ## The judgment a lead actually owns There are two genuinely defensible positions, and the tradeoff between them is the question. One: make the rule language less expressive so the platform can promise absence, and absorb the complaints from authors who wanted a richer condition. Two: keep the language expressive and make the platform honest about what it cannot certify, absorbing the risk that a reviewer over-reads a silent verdict. A useful tiebreaker is who consumes the verdict and what they do on it. If a conflict-free verdict gates a deployment or is shown to an auditor, the guarantee is load-bearing and option 1 earns its cost. If it is advisory context for a human reviewer, option 3 plus option 4 is usually the better trade. What is not defensible is choosing neither and letting a timeout quietly stand in for a proof. Worst-case hardness also does not mean real tables are hard — many are settled quickly by ordinary search. That is an engineering bet about your inputs, and it is a fine bet to make. It is simply not a guarantee, and the contract should not pretend otherwise.

  • Which restriction of the condition language would put the conflict-free claim into P?
    Conditions limited to conjunctions of attribute-equals-value tests over a fixed schema. Two such rules can fire together exactly when no attribute is bound to two different values, so each pair is settled by comparing bindings attribute by attribute. The whole check is polynomial in rules times attributes, and the negative verdict comes free with the positive one.
  • What should the verdict say when the check cannot settle a table?
    It should say unknown, name what was exhausted, and state what was covered — which rule pairs were settled and which fragment of the language the conclusion holds for. Folding unknown into conflict-free converts a statement about your run into a statement about every request, which is exactly the claim you could not support.
  • Does a co-NP-hardness result mean real policy tables are hard to check?
    No. Hardness is a worst-case statement about the problem family, and typical tables often fall to ordinary search quickly. The distinction matters for the contract: fast on your current inputs is an empirical bet that can break as rule authors get more inventive, whereas a language restriction is a bound that holds by construction.

saying these in an interview costs you the question

  • Promises a proof of absence without bounding the condition language.
  • Thinks a bigger timeout or more machines changes which class the claim lives in.
  • Reports no conflict found within the budget as conflict-free.
  • Assumes enumerating all attribute combinations is fine because the attributes look few.
  • Concludes from co-NP-hardness that every real table is impossible to check.