A binary relation R ⊆ Σ∗ × Σ∗ is called polynomially honest
if there exists a polynomial function p such that ⟨x, y⟩ ∈ R only if
|x| ≤ p(|y|) and |y| ≤ p(|x|). A function f ∶ Σ∗ → Σ∗ is polynomially honest if the relation {⟨x,f(x)⟩ ∶ x ∈ Σ∗} is polynomially honest. Prove that
A ⊆ Σ∗ is in NP if and only if A = Range(f) for some polynomially honest
function
f ∈ FP.