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:

  1. $+, - , *, /$ however desired
  2. $()$ however desired
  3. 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?

  • $\begingroup$ The link gives examples IT DOES NOT VERIFY OR DISCUSS my claims. :) $\endgroup$ – frogeyedpeas Aug 29 '13 at 22:30
  • $\begingroup$ What are the possible values for $V$? In your examples, you give $1$, $0$, $-1$. $\endgroup$ – J.-E. Pin Aug 30 '13 at 6:50
  • $\begingroup$ What do you mean by incomputable numbers of terms? $\endgroup$ – J.-E. Pin Aug 30 '13 at 6:52
  • $\begingroup$ the values of V i will restrict of 1,0,-1. $\endgroup$ – frogeyedpeas Sep 11 '13 at 19:21
  • $\begingroup$ incomputable number of terms = number of terms grow at a rate that faster than any polynomial on the # of bit used to represent the input $\endgroup$ – frogeyedpeas Sep 11 '13 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.