non primitive recursive algorithms having polynomial time verification?

Question

i think the title speaks for itself,

since the defining trait for NP class is that - they are the set of decision problems verifiable in polynomial time by a deterministic Turing machine.

thus it shouldn't matter if the algorithm computing the function belongs to any particular class - exp or factorial, even non-PR , as long as they are computable, but i am unable to find any specific example.

if there aren't any known such algorithms or problems, can it be proven that they atleast should exist ?

Answer 1

So let say you have an algorithm A that takes an input I and after some computation gives an output O.

Let say you have an algorithm V that can verify A, meaning that it takes an input (I, O, C) and compute in polynomial time (of the size of I) an output B such that for at least one C, if A(I)=O then V(I,O,C)=True

We say that C is a certificate

But if V computes in polynomial time (of the size of I), then the size of C is bound by a polynomial P (of the size of I). As for all couple I, O such that A(I)=O, there is at least one C, we can try all C of size lower or equal to P(|I|).

Note this is the same for O.

So for any I, the complexity of finding O is bounded by some exponential of a polynomial. (We try all possible O and C bounded by a fixed polynomial. Note that for decision problem, it's less work as O is a boolean)

So A can have any complexity (you can always add useless complexity), but there exist an algorithm computing the same thing as A that will be bound by some exp(P(s)).