Representing FP relations using witnesses Let a relation $R$ be A-polynomial if there is a polynomial $p$ and a polytime algorithm $A$ such that for each $x$:

If $(x,y) \in R$ then there is a witness $w$ of length at most $p(|x|)$ such that $A(x,w) = y$.
For each $w$ such that $A(x,w)$ halts, we have $(x,A(x,w)) \in R$.

Prove or disprove: Each $R$ in FP is A-polynomial.

My attempt: I think the statement is incorrect, and so I'm looking for a counterexample. Let $R$ be a relation in FP where the algorithm $A$ helps us decide the undecidable halting problem. I thought maybe about $R= \left\{0,1\right\}^*\times \left\{0,1\right\}^*$, but perhaps there is a simpler counterexample?
An $A$-polynomial relation can't have two many pairs agreeing on the first coordinate. Namely for any $x$ there can be at most $2^{p(x)}$ $y$'s such that $(x,y)\in R$. This shows that the simple relation $R=\{0,1\}^*\times\{0,1\}^*$ is in FP but not A-polynomial.