34
$\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?

Improve this question
$\endgroup$
3
  • 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, 2016 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, 2016 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, 2016 at 10:43

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Expected this to not be the case. Great answer! $\endgroup$
    – Filip Haglund
    Dec 7, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't understand #2. What implies that the different algorithm runs in polynomial time? $\endgroup$
    – Albert Hendriks
    Apr 25, 2018 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$
    – user541686
    Apr 25, 2018 at 22:10

Your Answer

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

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