There exist a constant c and an algorithm A such that for every Yes$-$instance

x of the problem P$,$ there is a string s of length at most $$x$$c with the property that A outputs Yes on input $($x$,$s$)$