Abstract. We introduce the binary value principle, which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, based on a well-known hypothesis by Shub and Smale about the hardness of computing factorials, where IPS is the strong algebraic proof system introduced by Grochow and Pitassi [ J. ACM, 65 (2018), 37]. Conversely, we show that short IPS refutations of this instance bridge the gap between sufficiently strong algebraic and semialgebraic proof systems. Our results extend to unrestricted IPS the paradigm introduced by Forbes, Shpilka, Tzameret, and Wigderson [ Theory Comput., 17 (2021), pp. 1–88], whereby lower bounds against subsystems of IPS were obtained using restricted algebraic circuit lower bounds, and demonstrate that the binary value principle captures the advantage of semialgebraic over algebraic reasoning, for sufficiently strong systems. Specifically, we show the following. (1) Conditional IPS lower bounds: The Shub–Smale hypothesis [ Duke Math. J., 81 (1995), pp. 47–54] implies a superpolynomial lower bound on the size of IPS refutations of the binary value principle over the rationals defined as the unsatisfiable linear equation [Formula: see text] for Boolean [Formula: see text]’s. Further, the related and more widely known [Formula: see text]-conjecture [ Duke Math. J., 81 (1995), pp. 47–54] implies a superpolynomial lower bound on the size of IPS refutations of a variant of the binary value principle over the ring of rational functions. No prior conditional lower bounds were known for IPS or apparently weaker propositional proof systems such as Frege systems (though our lower bounds do not translate to Frege lower bounds since the hard instances are not Boolean formulas). (2) Algebraic versus semialgebraic proofs: Admitting short refutations of the binary value principle is necessary for any algebraic proof system to fully simulate any known semialgebraic proof system, and for strong enough algebraic proof systems it is also sufficient. In particular, we introduce a very strong proof system that simulates all known semialgebraic proof systems (and most other known concrete propositional proof systems), under the name Cone Proof System (CPS), as a semialgebraic analogue of the IPS: CPS establishes the unsatisfiability of collections of polynomial equalities and inequalities over the reals, by representing sum-of-squares proofs (and extensions) as algebraic circuits. We prove that IPS polynomially simulates CPS iff IPS admits polynomial-size refutations of the binary value principle (for the language of systems of equations that have no 0/1-solutions), over both [Formula: see text] and [Formula: see text].

We introduce the binary value principle which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, based on a well-known hypothesis by Shub and Smale about the hardness of computing factorials, where IPS is the strong algebraic proof system introduced by Grochow and Pitassi (2018). Conversely, we show that short IPS refutations of this instance bridge the gap between sufficiently strong algebraic and semi-algebraic proof systems. Our results extend to full-fledged IPS the paradigm introduced in Forbes et al. (2016), whereby lower bounds against subsystems of IPS were obtained using restricted algebraic circuit lower bounds, and demonstrate that the binary value principle captures the advantage of semi-algebraic over algebraic reasoning, for sufficiently strong systems. Specifically, we show the following:

Tropical algebra is an emerging field with a number of applications in various areas of mathematics. In many of these applications appeal to tropical polynomials allows studying properties of mathematical objects such as algebraic varieties from the computational point of view. This makes it important to study both mathematical and computational aspects of tropical polynomials. In this paper we prove a tropical Nullstellensatz, and moreover, we show an effective formulation of this theorem. Nullstellensatz is a natural step in building algebraic theory of tropical polynomials and its effective version is relevant for computational aspects of this field. On our way we establish a simple formulation of min-plus and tropical linear dualities. We also observe a close connection between tropical and min-plus polynomial systems.

We investigate models of the mitogenactivated protein kinases (MAPK) network, with the aim of determining where in parameter space there exist multiple positive steady states. We build on recent progress which combines various symbolic computation methods for mixed systems of equalities and inequalities. We demonstrate that those techniques benefit tremendously from a newly implemented graph theoretical symbolic preprocessing method. We compare computation times and quality of results of numerical continuation methods with our symbolic approach before and after the application of our preprocessing.

We consider the problem of determining multiple steady states for positive real values in models of biological networks. Investigating the potential for these in models of the mitogen-activated protein kinases (MAPK) network has consumed considerable effort using special insights into the structure of corresponding models. Here we apply combinations of symbolic computation methods for mixed equality/inequality systems, specifically virtual substitution, lazy real triangularization and cylindrical algebraic decomposition. We determine multistationarity of an 11-dimensional MAPK network when numeric values are known for all but potentially one parameter. More precisely, our considered model has 11 equations in 11 variables and 19 parameters, 3 of which are of interest for symbolic treatment, and furthermore positivity conditions on all variables and parameters.

We study non-holonomic overideals of a left differential ideal J ⊂ F[θx, θy] in two variables where F is a differentially closed field of characteristic zero. One can treat the problem of finding non-holonomic overideals as a generalization of the problem of factoring a linear partial differential operator. The main result states that a principal ideal J = generated by an operator P with a separable symbol symb(P) has a finite number of maximal non-holonomic overideals; the symbol is an algebraic polynomial in two variables. This statement is extended to non-holonomic ideals J with a separable symbol. As an application we show that in case of a second-order operator P the ideal has an infinite number of maximal non-holonomic overideals iff P is essentially ordinary. In case of a third-order operator P we give sufficient conditions on in order to have a finite number of maximal non-holonomic overideals. In the Appendix we study the problem of finding non-holonomic overideals of a principal ideal generated by a second order operator, the latter being equivalent to the Laplace problem. The possible application of some of these results for concrete factorization problems is pointed out.

Loewy's decomposition of a linear ordinary differential operator as the product of largest completely reducible components is generalized to partial differential operators of order three in two variables. This is made possible by considering the problem in the ring of partial differential operators where both left intersections and right divisors of left ideals are not necessarily principal. Listings of possible decomposition types are given. Many of them are illustraded by worked out examples. Algorithmic questions and questions of uniqueness are discussed in the Summary.

Starting from the well-known factorization of linear ordinary differential equations, we define the generalized Loewy decomposition for a D-module. To this end, for any module I, overmodules J ⊇ I are constructed. They subsume the conventional factorization as special cases. Furthermore, the new concept of the module of relative syzygies Syz(I,J) is introduced. The invariance of this module and its solution space w.r.t. the set of generators is shown. We design an algorithm which constructs the Loewy-decomposition for finite-dimensional and some kinds of general D modules. These results are applied for solving various second- and third-order linear partial differential equations.

Proof systems for polynomial inequalities in 0-1 variables include the well-studied Cutting Planes proof system (CP) and the Lovász- Schrijver calculi (LS) utilizing linear, respectively, quadratic, inequalities. We introduce generalizations LS d of LS involving polynomial inequalities of degree at most d . Surprisingly, the systems LS d turn out to be very strong. We construct polynomial-size bounded degree LS d proofs of the clique-coloring tautologies (which have no polynomial-size CP proofs), the symmetric knapsack problem (which has no bounded degree Positivstellensatz Calculus (PC) proofs), and Tseitin’s tautologies (hard for many known proof systems). Extending our systems with a division rule yields a polynomial simulation of CP with polynomially bounded coefficients , while other extra rules further reduce the proof degrees for the aforementioned examples. Finally, we prove lower bounds on Lovász-Schrijver ranks , demonstrating, in particular, their rather limited applicability for proof complexity.

In this paper we prove that, in the context of weak machines over $\Bbb R$, there are no sparse $\NP$-hard sets.

Let F be an algebraically closed field of zero characteristic, a polynomial @@@@ ∈ F[X1, … , Xn have a multiplicative complexity r and ƒ1, … ƒk ∈ F[X1, … , Xn] be some polynomials of degrees not exceeding d, such that @@@@ = ƒ1 = ··· = ƒk = 0 has a finite number of roots. We show that the number of possible distinct vectors of multiplicities of these roots is small when r, d and k are small. As technical tools we design algorithms which produce Gröbner bases and vectors of multiplicities of the roots for a parametric zero-dimensional system. The complexities of these algorithms are singly exponential. We also describe an algorithm for parametric absolute factorization of multivariate polynomials. This algorithm has subexponential complexity in the case of a small (relative to the number of variables) degree of the polynomials.

Two important algebraic proof systems are the Nullstellensatz system and the polynomial calculus (also called the Grobner system). The Nullstellensatz system is a propositional proof system based on Hilbert's Nullstellensatz, and the polynomial calculus (PC) is a proof system which allows derivations of polynomials, over some field. The complexity of a proof in these systems is measured in terms of the degree of the polynomials used in the proof. The mod p counting principle can be formulated as a set MOD/sub p//sup n/ of constant-degree polynomials expressing the negation of the counting principle. The Tseitin mod p principles, TS/sub n/(p), are translations of the MOD/sub p//sup n/ into the Fourier basis. The present paper gives linear lower bounds on the degree of polynomial calculus refutations of MOD/sub p//sup n/ over p fields of characteristic q /spl ne/ p and over rings Z/sub q/ with q,p relatively prime. These are the first linear lower bounds for the polynomial calculus. As it is well-known to be easy to give constant degree polynomial calculus (and even Nullstellensatz) refutations of the MOD/sub p//sup n/ polynomials over F/sub p/, our results imply that the MOD/sub p//sup n/ polynomials have a linear gap between proof complexity for the polynomial calculus over F/sub p/ and over F/sub q/. We also obtain a linear gap for the polynomial calculus over rings Z/sub p/ and Z/sub q/ where p, q do not have identical prime factors.

This paper gives nearly optimal lower bounds on the minimum degree of polynomial calculus refutations of Tseitin's graph tautologies and the mod p counting principles, p >_ 2. The lower bounds apply to the polynomial calculus over fields or rings.These are the first linear lower bounds for polynomial calculus; moreover, they distinguish linearly between proofs over fields of characteristic p and T, y # r, and more generally distinguish linearly the rings Z, and Z, where 4 and P do not have the identical prime factors.

We use the known linear lower bound for Tseitin's tautologies for establishing linear lower bounds on the degree of Nullstellensatz proofs (in the usual boolean setting) for explicitly constructed systems of polynomials of a constant (in our construction 6) degree. It holds over any field of characteristic distinct from 2. Previously, a linear lower bound was proved for an explicitly constructed system of polynomials of a logarithmic degree.

A depth 3 arithmetic circuit can be viewed as a sum of products of linear functions. We prove an exponential complexity lower bound on depth 3 arithmetic circuits computing some natural symmetric functions over a finite field F. Also, we study the complexity of the functions f: D/sup n//spl rarr/F for subsets D/spl sub/F. In particular, we prove an exponential lower bound on the complexity of a depth 3 arithmetic circuit which computes the determinant or the permanent of a matrix considered as functions f:(F*)n/sup 2//spl rarr/F.

Given a set of semi-algebraic obstacles in the plane and two points in the same connected component of the complement, the problem is to construct the shortest path between these points in a given homotopy class.This path is unique and has some canonical form.We use the representation of homotopy classes in a way that is as general as the classical one.It consists in representing generators of a free group which describes the classes of homotopy by disjoint cuts [GS97] homeomorphic to rays.We show that given such a system of generators and a word representing a homotopy class, one can contruct the shortest path of this class in time polynomial in the size of the word and in the size of the representation of the obstacles and the cuts.The homotopy class may also be represented by a path, then the polynomial complexity will depend on the size of the representation of this path.As a technical notion we i n troduce one particular system of cuts, which we call an extremity basis, that proves to be especially convenient for algorithmic purposes.The considered problem is motivated by robot motion planning and by theoretical questions arising in shortest path approximations in higher dimensions.

International audience

AbatractWe prove the first exponential lower bound on the size of any depth 3 arithmetic circuit with unbounded fanin computing an explicit function (the determinant) over an arbitrary finite field.This answers an open problem of [N91] and [NW951 for the cs~e of finite fields.We intepret here arithmetic circuits in the algebra of polynomials over the given field.The proof method involves a new argument on the rank of linear functions, and a group symmetry on polynomials vanishing at certain nonsingular matrices, and could be of independent interest.

We design an algorithm for computing the generalized (algebraic circuits with root extracting; cf.\ Pippenger [J. Comput. System Sci., 22 (1981), pp. 454--470], Ja'Ja' [Proc. 22nd IEEE FOCS, 1981, pp. 95--100], Grigoriev, Singer, and Yao [ SIAM J. Comput., 24 (1995), pp. 242--246]) additive complexity of any rational function. It is the first computability result of this sort on the additive complexity of algebraic circuits.

We prove Ω(n²) complexity lower bound for the general model of randomized computation trees solving the Knapsack Problem, and more generally Restricted Integer Programming. This is the first nontrivial lower bound proven for this model of computation. The method of the proof depends crucially on the new technique for proving lower bounds on the border complexity of a polynomial which could be of independent interest.

In this paper, we study the computational power of real Turing machines over binary inputs. Our main result is that the class of binarysets that can be decided by real Turing machines in parallel polynomial time is exactly the class PSPACE/poly.

Article Free Access Share on Testing shift-equivalence of polynomials using quantum machines Author: D. Grigoriev Department of Computer Science & Department of Mathematics, Penn State University, University Park, PA Department of Computer Science & Department of Mathematics, Penn State University, University Park, PAView Profile Authors Info & Claims ISSAC '96: Proceedings of the 1996 international symposium on Symbolic and algebraic computationOctober 1996 Pages 49–54https://doi.org/10.1145/236869.236897Online:01 October 1996Publication History 6citation176DownloadsMetricsTotal Citations6Total Downloads176Last 12 Months4Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on A lower bound for randomized algebraic decision trees Authors: Dima Grigoriev Dept. of Computer Science and Mathematics, Penn State University, University Park Dept. of Computer Science and Mathematics, Penn State University, University ParkView Profile , Marek Karpinski Dept. of Computer Science, University of Bonn, 53117, Bonn Dept. of Computer Science, University of Bonn, 53117, BonnView Profile , Friedhelm Meyer auf der Heide Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098 Paderborn Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098 PaderbornView Profile , Roman Smolensky Dept. of Computer Science, University of Bonn, 53117, Bonn Dept. of Computer Science, University of Bonn, 53117, BonnView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 612–619https://doi.org/10.1145/237814.238011Published:01 July 1996Publication History 12citation385DownloadsMetricsTotal Citations12Total Downloads385Last 12 Months13Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We prove for the first time an existence of the short (polynomial size) proofs for nondivisibility of two sparse polynomials (putting thus this problem is the class NP) under the Extended Riemann Hypothesis. The divisibility problem is closely relate

We introduce a new method of proving lower bounds on the depth of algebraic decision trees of degree d and apply it to prove a lower bound /spl Omega/(log N) for testing membership to an n-dimensional convex polyhedron having N faces of all dimensions, provided that N>(nd)/sup /spl Omega//(n). This weakens considerably the restriction on N previously imposed by the authors and opens a possibility to apply the bound to some naturally appearing polyhedra.

Article Free Access Share on Algorithms for computing sparse shifts for multivariate polynomials Authors: Dima Yu. Grigoriev Department of Computer Science and Department of Mathematics, Pennsylvania State University, State College, PA Department of Computer Science and Department of Mathematics, Pennsylvania State University, State College, PAView Profile , Y. N. Lakshman Department of Mathematics and Computer Science, Drexel University, Philadelphia, PA Department of Mathematics and Computer Science, Drexel University, Philadelphia, PAView Profile Authors Info & Claims ISSAC '95: Proceedings of the 1995 international symposium on Symbolic and algebraic computationApril 1995 Pages 96–103https://doi.org/10.1145/220346.220359Online:01 April 1995Publication History 8citation211DownloadsMetricsTotal Citations8Total Downloads211Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let $\rho$ be a set of algebraic expressions constructed with radicals and arithmetic operations, and which generate the splitting field F of some polynomial. Let $N_{\beta}(\rho)$ be the minimum total number of root-takings and exponentiations used in any straightline program for computing the functions in $\rho$ by taking roots, exponentials, logarithms, and performing arithmetic operations. In this paper it is proved that $N_{\beta}(\rho) = v(G)$, where $v(G)$ is the minimum length of any cyclic Jordan-Hölder tower for the Galois group G of F. This generalizes a result of Ja’Ja’ [Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science, 1981, pp. 95–100], and shows that the inclusion of certain new primitives, such as taking exponentials and logarithms, does not improve the cost of computing such expressions as compared with programs that use only root-takings.

We consider computation trees which admit as gate functions along with the usual arithmetic operations also algebraic or transcendental functions like exp, log, sin, square root (defined in the relevant domains) or much more general, Pfaffian functions. A new method for proving lower bounds on the depth of these trees is developed which allows to prove a lower bound /spl Omega/(/spl radic/(log N)) for testing membership to a convex polyhedron with N facets of all dimensions, provided that N is large enough. This method differs essentially from the previous approaches adopted for algebraic computation trees.>

We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound \\Omega\\Gammand/ N) for testing membership to a convex polyhedron having N facets of all dimensions, provided that N is large enough. This bound apparently does not follow from the methods developed by M. Ben-Or, A. Bjorner, L. Lovasz, and A. Yao ([B 83], [BLY 92]) because the topological invariants used in these methods become trivial for a convex polyhedra. Departments of Computer Science and Mathematics, Penn State University, University Park, PA 16802, Email: [email protected]. Supported in part by the Volkswagen-- Stiftung. y Department of Computer Science, University of Bonn, 53117 Bonn, and the International Computer Science Institute, Berkeley, California. Research supported in part by DFG Grant KA 673/4--1, by the ESPRIT BR Grants 7097 and ECUS030, and by the Volkswagen-Stiftung. Email: [email protected] z Departments of Computer Science and Mathemat...

The authors analyze the computational complexity of sparse rational interpolation, and give the first deterministic algorithm for this problem with singly exponential bounds on the number of arithmetic operations.

Article Free Access Share on Existence of short proofs for nondivisibility of sparse polynomials under the extended Riemann hypothesis Authors: Dima Yu. Grigoriev View Profile , Marek Karpinski View Profile , Andrew M. Odlyzko View Profile Authors Info & Claims ISSAC '92: Papers from the international symposium on Symbolic and algebraic computationAugust 1992 Pages 117–122https://doi.org/10.1145/143242.143287Online:01 August 1992Publication History 5citation182DownloadsMetricsTotal Citations5Total Downloads182Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The authors design the first polynomial time (for an arbitrary and fixed field GF(q)) ( in , delta )-approximation algorithm for the number of zeros of arbitrary polynomial f(x/sub 1/. . . x/sub n/) over GF(q). It gives the first efficient method for estimating the number of zeros and nonzeros of multivariate polynomials over small finite fields other than GF(2) (like GF(3)), the case important for various circuit approximation techniques. The algorithm is based on the estimation of the number of zeros of an arbitrary polynomial f(x/sub 1/. . .,x/sub n/) over GF(q) in the function of the number m of its terms. The bounding ratio is proved to be m/sup (q-1)/log/sup q/.>

We present two algorithms for interpolating sparse rational functions.The first is the interpolation algorithm in a sense of sparse partial fraction representation of rational functions.The second is the algorithm for computing the entier and the remainder of a rational function.The first algorithm works without apriori known bound on the degree of a rational function, the second one is in the parallel class NC provided that the degree is known.The presented algorithms complement the sparse interpolation results of [GKS 90].

The authors present the first algorithm for the (black box) interpolation of t-sparse, n-variate, rational functions without knowing bounds on exponents of their sparse representation, with the number of queries independent of exponents. In fact, the algorithm uses O(nt/sup t/) queries to the black box, and it can be implemented for a fixed t in a polynomially bounded storage (or polynomial parallel time).>

A subexponential-time algorithm is designed which finds the number of connected components of a semi-algebraic set given by a quantifier-free formula of the first-order theory of real closed fields (for a rather wide class of real close fields, cf. [GV 88], [Gr 88]). Moreover, the algorithm allows for any two points from the semi-algebraic set to test, whether they belong to the same connected component.

Let a system of linear ordinary differential equations of the first order Y′ = AY be given, where A is n × n matrix over a field F(X), assume that the degree degX(A) < d and the size of any coefficient occurring in A is at most M. The system Y′ = AY is called reducible if it is equivalent (over the field F(X)) to a system Y&prime1 = A1Y1 with a matrix A1 of the form A1 = (A1,1 0) (A2,1 A2,2)

The authors consider the problem of reconstructing (i.e., interpolating) a t-sparse multivariate polynomial given a black box which will produce the value of the polynomial for any value of the arguments. It is shown that, if the polynomial has coefficients in a finite field $GF[q]$ and the black box can evaluate the polynomial in the field $GF[q^{\ulcorner 2\log_{q}(nt)+3 \urcorner}]$, where n is the number of variables, then there is an algorithm to interpolate the polynomial in $O(\log^3 (nt))$ boolean parallel time and $O(n^2 t^6 \log^2 nt)$ processors. This algorithm yields the first efficient deterministic polynomial time algorithm (and moreover boolean $NC$-algorithm) for interpolating t-sparse polynomials over finite fields and should be contrasted with the fact that efficient interpolation using a black box that only evaluates the polynomial at points in $GF[q]$ is not possible (cf. [M. Clausen, A. Dress, J. Grabmeier, and M. Karpinski, Theoret. Comput. Sci., 1990, to appear]). This algorithm, together with the efficient deterministic interpolation algorithms for fields of characteristic 0 (cf. [D. Yu. Grigoriev and M. Karpinski, in Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 166–172], [M. Ben-Or and P. Tiwari, in Proceedings of the 20th ACM Symposium on the Theory of Computing, 1988, pp. 301–309]), yields for the first time the general deterministic sparse conversion algorithm working over arbitrary fields. (The reason for this is that every field of positive characteristic contains a primitive subfield of this characteristic, and so this method can be applied to the slight extension of this subfield.) The method of solution involves the polynomial enumeration techniques of [D. Yu. Grigoriev and M. Karpinski, op. cit.] combined with introducing a new general method of solving the problem of determining if a t-sparse polynomial is identical to zero by evaluating it in a slight extension of the coefficient field (i.e., an extension whose degree over this field is logarithmic in nt).

It is shown that the problem of deciding and constructing a perfect matching in bipartite graphs G with the polynomial permanents of their n × n adjacency matrices A (perm(A) = nO(1)) are in the deterministic classes NC2 and NC3, respectively. We further design an NC3 algorithm for the problem of constructing all perfect matchings (enumeration problem) in a graph G with a permanent bounded by O(nk). The basic step was the development of a new symmetric functions method for the decision algorithm and the new parallel technique for the matching enumerator problem. The enumerator algorithm works in O(log3 n) parallel time and O(n3k+5.5 · log n) processors. In the case of arbitrary bipartite graphs it yields an 'optimal' (up to the log n- factor) parallel time algorithm for enumerating all the perfect matchings in a graph. It entails also among other things an efficient NC3-algorithm for computing small (polynomially bounded) arithmetic permanents, and a sublinear parallel time algorithm for enumerating all the perfect matchings in graphs with permanents up to 2nε.