In an answer to a question regarding input validation in decision problems, @Apass Jack wrote

It is easy to check whether a problem instance is a valid instance or not for almost all decision problems people have been interested in. It is so easy and so common that people have become so sloppy or efficient that this verification step is usually skipped or even forgotten in the specification of an algorithm. That might be the source of your confusion.

Are there (non-pathological) decision problems for which input validation is as complex or more complex than computing the actual decision for an already validated input?

  • $\begingroup$ Well, what about "$G$ is a Hamiltonian graph which contains an odd cycle"? $\endgroup$ – dkaeae Mar 18 '19 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.