33
$\begingroup$

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?

$\endgroup$
  • 8
    $\begingroup$ Perhaps I misunderstand, but why is the following not a polynomial-time verification algorithm? Given $(x,y)$, compute the function $f(x)$ yourself, using the polynomial-time algorithm, and return "correct" if $f(x)=y$. Is it possible that you misread or the professor misspoke and meant instead to say that there are problems verifiable in polynomial time but not solvable in polynomial time? $\endgroup$ – Lieuwe Vinkhuijzen Dec 7 '16 at 12:01
  • 1
    $\begingroup$ @LieuweVinkhuijzen "to say that there are problems verifiable in polynomial time but not solvable in polynomial time?" [ref. needed] $\endgroup$ – T. Verron Dec 8 '16 at 8:58
  • $\begingroup$ @T.Verron Haha yes, I too would be very happy to see the professor's proof for this claim ;) $\endgroup$ – Lieuwe Vinkhuijzen Dec 8 '16 at 10:43
44
$\begingroup$

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 $n \in \mathbb{N}$ (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 $N$s 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.

$\endgroup$
  • 1
    $\begingroup$ Expected this to not be the case. Great answer! $\endgroup$ – Filip Haglund Dec 7 '16 at 16:37
  • 7
    $\begingroup$ This does not answer the question. The OP specifically asked for a problem not verifiable in the usual sense, where, in addition to the input and the alleged answer, we get a certificate $z$ which certifies the correctness of the answer. In your case, the certificate is the bits used to nondeterministically generate the new equivalent Turing Machine. Given $M, N$ and $z$, it is easy to check whether $z$ gives the machine $M$. Without $z$, the question is whether it is easy to generate hard instances of (NPC) languages, which is only true in Minicrypt and Cryptomania. $\endgroup$ – Lieuwe Vinkhuijzen Dec 7 '16 at 17:43
  • 2
    $\begingroup$ @chi Not all pairs $M, N$ can be certified, but the set of pairs $M, N$ generated by your algorithm can be certified. The certificate is the transcript of your algorithm producing $N$ from $M$ (e.g. "start with $M$, then add this state, and add this transition, then... and voilà, $N$!"). In general, if $T$ is a nondeterministic algorithm which, given $x$, always computes an admissible $y$, then a transcript of a computation path of $T(x)$ is a certificate that a given $y$ is admissible. $\endgroup$ – Lieuwe Vinkhuijzen Dec 7 '16 at 20:36
  • 3
    $\begingroup$ @chi There is a slight nuance in the question: For an arbitrary relation $R$, it is possible that not all admissible $y$ are certifiable, and you give an elegant example. However, the question does not ask whether admissible but uncertifiable relations exist (the answer is yes, by your example), instead it asks whether we can have an algorithm which produces admissible, uncertifiable output. The answer, here, must be no, because of the argument above. $\endgroup$ – Lieuwe Vinkhuijzen Dec 7 '16 at 20:42
  • 2
    $\begingroup$ @chi I don't know what the OP intended to ask, but I found your answer very illuminating nonetheless, I learned something! imo the question can be read the way you do, or equally plausibly as "do one-way functions exist?" (maybe) or "are hard instances of NP problems easy to generate?" (I hope so for RSA), or, the way I read it, as "Is $NP\subsetneq P$?" (no). $\endgroup$ – Lieuwe Vinkhuijzen Dec 7 '16 at 22:16
1
$\begingroup$

This is merely an elaboration of the first sentence of @chi's answer, since I did not find it obvious.

The idea is, if you have an algorithm that finds the answer to some problem in polynomial time, then there are two possibilities:

  1. You have previously proven (mathematically) that the algorithm's output is a solution to the problem, in which case, the algorithm's steps themselves form the proof of correctness.

  2. You have a different algorithm for checking that the output is indeed a solution, in which case you must be running this algorithm (otherwise you'd be falling under case #1), which implies you're doing it in polynomial time.

Therefore, there can be no such problem.

$\endgroup$
  • $\begingroup$ I don't understand #2. What implies that the different algorithm runs in polynomial time? $\endgroup$ – Albert Hendriks Apr 25 '18 at 22:07
  • $\begingroup$ @AlbertHendriks: If the verifier didn't run in polynomial time then the original solver could not claim to have found a correct solution in polynomial time, because it needs to run the verifier to make sure its solution is correct. $\endgroup$ – Mehrdad Apr 25 '18 at 22:10

Your Answer

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

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