Complexity of (SAT to 3-SAT) Problem?

It is well known that any CNF formula can be transform in polynomial time into a 3-CNF formula by using new variables (see here). If using new variables is not allowed, it is not always possible (take for instance the single clause formula : $(x_1 \lor x_2 \lor x_3 \lor x_4)$).

Let define the (SAT to 3-SAT) problem : Given $F$, a CNF formula. Is it possible to transform $F$ into an equivalent 3-CNF defined on the same variables as $F$ ? - where "equivalent" means with the same set of models.

What is the complexity of this problem ?

Edit : It has been shown on cstheory that the problem is co-NP hard.

This has been answered on the CS Theory StackExchange site:
https://cstheory.stackexchange.com/a/19833/5038

(I'm posting an answer here, so this question does not get treated as a question-without-an-answer and get periodically rotated back onto the front page by the Community user. Normally, questions without any upvoted or accepted answer are re-displayed on the front page every so often. Since this question now has been solved answered elsewhere, there doesn't seem any need for that. As long as someone upvotes or accepts this answer, that should prevent this question from being rotated back onto the front page. I'm ticking the community wiki box so I won't get any rep from this answer.)

StackExchange Computer Science Q#16741, answer score: 4