Problems Solvable in Poly time but not verifiable in Poly time

Question

I was just wondering if there exists problems that are solvable in polynomial time (a correct solution can be found in polynomial time) but not verifiable in polynomial time. My professor says no, but doesn't rlly give a clear explanation besides saying you can just use the solution to verify, but I fail to see how this can be if there are more than just one solution.

Are we allowed to make the argument that any problem with a poly algorithm can be modified in polynomial time so that it produces the particular polynomial solution we are trying to verify?

Edit: Sorry if the problem was confusing as I threw in P and NP, the title has been changed to reflect this.

Answer 1

It appears you're asking about problems for which there may be more than one correct answer for a given input (not decision problems).

In that case, there may exist a polynomial-time algorithm that finds a solution, but no algorithm that can verify arbitrary solutions. For example, given any string, it's easy to find a program that prints that string and then halts, but impossible in general to determine whether a program prints that string and then halts.

Answer 2

The verification algorithm will just use the solving algorithm and will ignore the verification "proof" it gets.

I.e, a verifier is a TM $V(x,w)$, such that $x\in L\iff \exists w, |w|\text{ is polynomial and } V(x,w)=true$.

Therefore, if $V$ completely ignores $w$ and uses the solving procedure to check if $x\in L$, it is a polynomial verifier. The algorithm of $V$ is as follows:

define $V(x,w)$:

1. Compute $S(x)$
2. Return "true" $\iff$ $S$ returned "true"

So basically, $w$ has no meaning here. Its pretty "hacky" and sounds weird, but it is allowed since there is a polynomial solver $S$ - and polynomial solvers are (in some sense) stronger than polynomial verifiers.

Answer 3

You have a problem in P. This means you have an algorithm X that will tell you whether the answer for an instance is yes or no, in polynomial time.

Now I create a verifier. A verifier takes an instance and some information that is supposed to help it, and will return in polynomial time an answer “yes” if the correct answer is “yes” and the information is useful.

My verifier throws the extra information away, uses algorithm X to determine the correct answer in polynomial time, and returns that answer. Since it gives the correct answer whenever the correct answer is yes, your problem is in NP - it exactly meets the definition for NP problems. Since it also gives the correct answer when the answer is no, P is also in co-NP.