There is a reasonable argument that your question is at least NP, and plausibly NP-hard or harder depending on how you formalize the verification oracle.