Before revision:  In general, this problem is shown to be \existsR-complete.
After revision:  In general, this problem is known to be \existsR-complete.