Witness existence

A witness-existence is some string \(w\) (or a proof or certificate) that testifies that \(x\in A\).

It asks if there is an input \(w\) to the program $V(x, w), a value of \(x\), and some \(t\) bounding the the witness size and algorithm runtime.