1
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, that is an excellent counterexample, thank you for this! $\endgroup$ Commented Dec 7, 2022 at 17:17
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ but how would you use the solving procedure to check? It seems a little blurry to me that any arbitrary solving procedure can be used to make the check. $\endgroup$ Commented Dec 6, 2022 at 18:05
  • $\begingroup$ I edited the answer a bit in hope to make clear exactly what $V$ does and why it is allowed. $\endgroup$
    – nir shahar
    Commented Dec 6, 2022 at 18:44
  • 1
    $\begingroup$ Got ya. That makes sense in terms of a decision problem. But what I'm proposing is given a solution to a problem that we can come up with in polynomial time, does there exist a verifier that takes $$\Omega(a^n)$$ to verify. So the solution is some concrete solution and not a decision problem. Does this change things? $\endgroup$ Commented Dec 6, 2022 at 19:14
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.