Computer Science – Computational Complexity
Scientific paper
2007-08-27
Computer Science
Computational Complexity
Scientific paper
A polynomial-time algorithm for computing the permanent in any field of characteristic 3 is presented in this article. The principal objects utilized for that purpose are the Cauchy and Vandermonde matrices, the discriminant function and their generalizations of various types. Classical theorems on the permanent such as the Binet-Minc identity and Borchadt's formula are widely applied, while a special new technique involving the notion of limit re-defined for fields of finite characteristics and corresponding computational methods was developed in order to deal with a number of polynomial-time reductions. All the constructions preserve a strictly algebraic nature ignoring the structure of the basic field, while applying its infinite extensions for calculating limits. A natural corollary of the polynomial-time computability of the permanent in a field of a characteristic different from 2 is the non-uniform equality between the complexity classes P and NP what is equivalent to RP=NP (Ref. [1]).
No associations
LandOfFree
A Polynomial-time Algorithm for Computing the Permanent in GF(3^q) 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 A Polynomial-time Algorithm for Computing the Permanent in GF(3^q), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Polynomial-time Algorithm for Computing the Permanent in GF(3^q) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-126273