  We focus on rational solutions or nearly-feasible rational solutions that
serve as certificates of feasibility for polynomial optimization problems. We
show that, under some separability conditions, certain cubic polynomially
constrained sets admit rational solutions. However, we show in other cases that
it is NP Hard to detect if rational solutions exist or if they exist of any
reasonable size. We extend this idea to various settings including near
feasible, but super optimal solutions and detecting rational rays on which a
cubic function is unbounded. Lastly, we show that in fixed dimension, the
feasibility problem over a set defined by polynomial inequalities is in NP by
providing a simple certificate to verify feasibility. We conclude with several
related examples of irrationality and encoding size issues in QCQPs and SOCPs.
