Mathematics – Logic
Scientific paper
2010-11-12
Mathematics
Logic
33 pages, revised and extended
Scientific paper
We introduce a general concept of complexity and a polynomial type algebraic complexity of a polynomial mapping. The notion of polynomial type algebraic complexity encompasses the determinantal complexity. We analyze the relation between polynomial type algebraic complexities and elusive functions. We study geometric-algebraic properties of polynomial type computational complexities. We present two algorithms to construct a test function for estimating a polynomial type algebraic complexity; one of them is based on Gr\"obner bases, the other uses the resultant of polynomials in many variables. We describe an algorithm to compute a polynomial type algebraic complexity of polynomial mappings defined over $C$. We develop the method by Kumar-Lokam-Patankar-Sarma that uses the effective elimination theory combined with algebraic number field theory in order to construct elusive functions and polynomial mappings with large circuit size. For $F = C$ or $R$, and for any given $r$, we construct explicit examples of sequences of polynomial mappings $f_n: F ^{2n} \to F ^n$ and of degree $5r+1$ whose coefficients are algebraic numbers such that any depth $r$ arithmetic circuit for $f_n$ is of size greater than $ n^2/(50 r^2)$. Using the developed methods we also construct concrete examples of polynomials with large determinantal complexity.
Lê Hông Vân
No associations
LandOfFree
Polynomial type algebraic complexities and elusive functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Polynomial type algebraic complexities and elusive functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial type algebraic complexities and elusive functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-204111