Finding a feasible solution to a special case system of inequalities $A^{\tau}A \cdot {\bf x} > {\bf 0}, {\bf x} > {\bf 0}$

Question

Given that $A^{\tau}A$ is full rank $N \times N$ and positive definite matrix.

Is it possible to find a ${\bf x} \epsilon R^N$ that satisfies the system below in polynomial time with an exact number of steps.

$A^{\tau}A \cdot {\bf x} > {\bf 0}$
${\bf x} > {\bf 0}$

The inverse of $A^{\tau}A$ exists it is available and assumed known if needed.

Some possible answers that are ruled out are:

• Simplex because is not polynomial
• Karmarkar methods and interior methods may be of polynomial time but they don't have an upper bound in the number of steps.

Anyway the above are more general methods that also apply when the number of constraints are bigger than $N$ and the table is not symmetric or positive definite. I am hoping for an exact solution to the smaller and more constrained (special) problem as it was stated above.

So the question is:

1. Do you know an existing algorithm that solves the above?
2. If not can you devise such an algorithm?
3. If not can you theorize why this is such a difficult problem?
4. If not can you give links that touch on the subject?