Inconclusive Algorithm

Definition

Inconclusive Algorithm

An inconclusive algorithm may return a distinguished outcome $\perp$ instead of a conclusive result $y\in Y$:

$$A:X\to Y\cup \{\perp \}.$$

It is inconclusive on input $x$ exactly when

$$A(x)=\perp .$$

This means that the algorithm makes no claim about the correct answer. For a decision predicate $P$,

$$A(x)=\perp /⟹P(x),A(x)=\perp /⟹\neg P(x).$$

Here, $\perp$ denotes “unknown”, not logical falsehood. Unlike a conclusive algorithm, an inconclusive algorithm does not always answer. It may nevertheless be sound because soundness requires only that every conclusive result be correct.

Example

Colour refinement

Colour refinement soundly rejects two graphs $G$ and $H$ when their stable colour signatures differ:

$$\mathrm{sig}(G)\ne \mathrm{sig}(H)⟹G\ncong H.$$

Equal signatures produce an inconclusive result because they establish neither isomorphism nor non-isomorphism:

$$\mathrm{sig}(G)=\mathrm{sig}(H)/⟹G\cong H,\mathrm{sig}(G)=\mathrm{sig}(H)/⟹G\ncong H.$$