Say you are given an arbitrary Algebraic Formula:
$$G(u_1,u_2,u_3...u_n) = 0$$
Where the expression $G$ is allowed to utilize:
- $+, - , *, /$ however desired
- $()$ however desired
- The operator $P(a_1,a_2,a_3... a_r, U, V)$
where $P$ specifies a polynomial over its inputs and $U$ denotes the polynomial itself, and V denotes whether polynomial is being applied or its inverse:
An example:
$P(x,G(x),1) = G(x)$ for any polynomial $G(x)$
$P(x,G(x),0) = G^{-1}(x)$ for any polynomial $G(x)$
Thus for example we can write the following:
$$P(3,x^2-x+7,-1) - \frac{1 + 4i}{2} =0$$
Verifying this basically involves solving the problem:
$x^2 - x + 7 = 3$ for x and seeing if $\frac{1 + 4i}{2}$ is a valid solution.
However as is well known (check this link if you want more http://www.math.uiuc.edu/~berndt/articles/radicals.pdf)
Some radical identities can become very complex and unwieldy to check yet are true. Additionally the P notation enables for identities between inverse functions that cannot be represented by radicals to exist. Brute force taking powers and polynomials could easily produce incomputable numbers of terms.
Can this problem be solved in polynomial time with respect to input size?