Your question amounts to treating construction problems in
geometry as decision problems, and so it makes sense to me to
adopt the terminology of computability theory. This same kind of
distinction arises in computability theory, where we have the
- A set $A$ is decidable if we can computably verify yes-or-no whether a given input $a$ is in $A$ or not.
- A set $A$ is semi-decidable if we can computably verify positive instances of $a\in A$.
- A set $A$ is co-semi-decidable if we can computably verify negative instances, that is, instances where $a\notin A$. (that is, the complement is semi-decidable)
This might at first suggest the terminology of
- semi-constructible, if you can constructibly verify positive
- co-semi-constructible if you can constructibly
verify failing instances.
But actually, since what you have is explicitly a decision
problem---namely, given this geometrical configuration, is it
acceptable?---I find it natural to use the terminology:
- constructibly decidable: if you can constructibly verify
- constructibly semi-decidable: if you can constructibly verify
positive instances. (or: constructibly verifiable)
- constructibly co-semi-decidable: if you can constructibly verify
negative instances. (or: constructibly co-verifiable)
This raises the question: is every constructibly decidable
construction problem also constructible? As Anton notes in the
comments, the answer is no, because the angle trisection problem
is both constructibly semi-decidable and constructibly
co-semi-decidable (and hence constructibly decidable), but not
So these are the interesting situations for which you can decide yes-or-no correctly in every instance whether a proposed solution to a construction is correct or not, but you cannot produce the solution constructibly. This phenomenon does not arise in classical computability theory, because of our ability there to computably enumerate the entire domain---in the context of the natural numbers, we can just keep trying every single number in order until we hit upon the "Yes" answer in order to find it. But in geometry, we cannot constructibly enumerate the entire (uncountable) space.
The same phenomenon arises in infinitary computability theory, where we have the lost-melody phenomenon, which occurs when there is an infinity binary string
$c$ such that one can computably verify (in the infinitary sense)
whether a given infinite string $x$ is equal to $c$ or not, but there is no infinitary computable procedure to produce $c$ from scratch. The "lost-melody" idea is that these
are like the song that you know well enough to say, "yes, that's
it!" or "no, that isn't it", but you cannot sing it on your own. The lost-melody phenomenon is known to occur in several distinct infinitary contexts, where we are not able computably to enumerate the domain.
Let me finish by mentioning that it would seem very natural to explore the analogues of P and NP in geometry. For example, a geometric construction problem would be constructibly P, if there is a construcible decision procedure taking suitably few steps (like polynomial time). It would be constructibly NP, if an input is acceptable just in case there are a (suitably few) extra points that can be added, such that the whole configuration can now be verified in (suitably few) steps.