Jump to text
On this page
Copy and source
Published source confirmed at last check

Source changed 2026-11-18 21:11:39 UTC · snapshot created 2026-11-18 21:12:35 UTC · last check 2026-11-18 22:15:20 UTC

CMP.1:2 - Problem

Two problems can have similar names or output shapes while admitting different inputs or requiring different guarantees. A conversion can lose the distinction that determines the answer, create a target input outside the solver’s domain, or leave no effective way to recover the original output.

A reduction can also be used backwards. Solving A through B supplies an A-solver when B is solvable; a known impossibility for A then constrains B. Reversing that implication can rule out a useful algorithm without justification.

The task is to construct the connection, establish its answer relation and effective execution, and carry only the consequence that its direction and resource conditions support.