Is there a task that is solvable in polynomial time but not verifiable in polynomial time?

A colleague of mine and I have just hit some notes of one of our professors. The notes state that there are tasks that are possible to solve in polynomial time (are in the class of PF) but that are NOT verifiable in polynomial time (are NOT in the class of NPF).

To elaborate about these classes: We get some input X and produce some output Y such that (X,Y) are in relation R representing our task. If it is possible to obtain Y for X in polynomial time, the task belongs to the class of PF. If it is possible to verify polynomial-length certificate Z that proves a tuple (X,Y) is in relation R in polynomial time, the task belongs to the class of NPF.

We are not talking about decision problems, where the answer is simply YES or NO (more formally if some string belongs to some language). For decision problems it appears that PF is a proper subset of NPF. However, for other tasks it might be different.

Do you know of a task that can be solved in polynomial time but not verified in polynomial time?

Answer

This is only possible if there are many admissible outputs for a given input. I.e., when the relation R is not a function because it violates uniqueness.

For instance, consider this problem:

Given nN (represented in unary) and a TM M, produce another TM N such that L(M)=L(N) and #N>n (where #N stands for the encoding (Gödel number) of N into a natural number)

Solving this is trivial: keep adding a few redundant states to the TM M, possibly with some dummy transitions between them, until its encoding exceeds n. This is a basic repeated application of the Padding Lemma on TMs. This will require n paddings, each of which can add one state, hence it can be done in polynomial time.

On the other hand, given n,M,N it is undecidable to check if N is a correct output for the inputs n,M. Indeed, checking L(M)=L(N) is undecidable (apply the Rice theorem), and the constraint #N>n only discards finitely many Ns from those. Since we remove a finite amount of elements from an undecidable problem, we still get an undecidable problem.

You can also replace the undecidable property L(M)=L(N) to obtain variations which are still computable but NP hard/complete. E.g. given n (in unary) it is trivial to compute a graph G having a n-clique inside. But given n,G it is hard to check whether a n-clique exists.

Attribution
Source : Link , Question Author : Drozi , Answer Author : chi

Leave a Comment