# Decision problem

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

A decision problem specifies an input set X and a yes-instance subset Y⊆X; a decider must terminate on every legal input and return the correct Boolean answer.

mko-decision-problem · definition · v0.10.0



## Mathematical statement

A decision problem is an input set X with a yes-instance set Y⊆X, equivalently a proposition-valued specification P:X→Prop. Relative to an explicit computational model, a decider D must terminate on every x∈X and satisfy D(x)=true exactly when x∈Y.





## Representative formula (exact TeX)

D:X\to B





## Assumptions


- The input set X and yes-instance set Y are fixed, with Y⊆X.
- A decidability claim also requires an effective input representation and computational model; a finite lookup table establishes decidability only for that finite X.





## Symbol scope


- D — candidate decider
- X — legal input set
- B — Boolean answer set





## Intuition, definition, and misconceptions

Separate the specification from its implementation: Y or P describes correct answers, while D is a candidate procedure. It is a decider only if it terminates and agrees with the specification on every input.

For an explicit finite X, a complete table can exhaustively check D. Agreement on samples does not establish agreement over the entire domain; outside-domain inputs are not part of the current problem.

General infinite input domains require effective encodings and a computational model. This finite slice infers neither general computability nor undecidability from lookup tables.

A semidecision procedure that recognizes only yes-instances is not automatically a total decider, and finite test success does not decide a general infinite problem.





## Adopted derivation guide

[Decision problem: proving that a trial-division procedure is a decider on an explicit finite input set](https://ocme.evemisslab.com/en/derivations/derivation-mko-decision-problem-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Set](https://ocme.evemisslab.com/en/mko/mko-set/) — Input domains and yes-instances are represented by sets.
- [Proposition](https://ocme.evemisslab.com/en/mko/mko-proposition/) — The specification P(x) is a proposition depending on the input.
- [Function mapping](https://ocme.evemisslab.com/en/mko/mko-function-mapping/) — A total decider gives one Boolean output for each legal input.





## Verification boundary

A finite input table permits complete specification/output comparison; no general decidability is asserted without a computational model.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Construct explicit semantic bridges among Prop specifications, Bool deciders, effective representations and abstract computational models.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/decision-problem.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-decision-problem/index.md)