ﻻ يوجد ملخص باللغة العربية
A perfect matching in an undirected graph $G=(V,E)$ is a set of vertex disjoint edges from $E$ that include all vertices in $V$. The perfect matching problem is to decide if $G$ has such a matching. Recently Rothvo{ss} proved the striking result that the Edmonds matching polytope has exponential extension complexity. Here for each $n=|V|$ we describe a perfect matching polytope that is different from Edmonds polytope and define a weaker notion of extended formulation. We show that the new polytope has a weak extended formulation (WEF) $Q$ of polynomial size. For each graph $G$ with $n$ vertices we can readily construct an objective function so that solving the resulting linear program over $Q$ decides whether or not $G$ has a perfect matching. The construction is uniform in the sense that, for each $n$, a single polytope is defined for the class of all graphs with $n$ nodes. The method extends to solve poly time optimization problems, such as the weighted matching problem. In this case a logarithmic (in the weight of the optimum solution) number of optimizations are made over the constructed WEF. The method described in the paper involves construction of a compiler that converts an algorithm given in a prescribed pseudocode into a polytope. It can therefore be used to construct a polytope for any decision problem in {bf P} which can be solved by a given algorithm. Compared with earlier results of Dobkin-Lipton-Reiss and Valiant our method allows the construction of explicit linear programs directly from algorithms written for a standard register model, without intermediate transformations. We apply our results to obtain polynomial upper bounds on the non-negative rank of certain slack matrices related to membership testing of languages in {bf P/Poly}.
We exhibit an algorithm to compute the strongest polynomial (or algebraic) invariants that hold at each location of a given affine program (i.e., a program having only non-deterministic (as opposed to conditional) branching and all of whose assignmen
The semantics of assignment and mutual exclusion in concurrent and multi-core/multi-processor systems is presented with attention to low level architectural features in an attempt to make the presentation realistic. Recursive functions on event seque
For each integer $n$ we present an explicit formulation of a compact linear program, with $O(n^3)$ variables and constraints, which determines the satisfiability of any 2SAT formula with $n$ boolean variables by a single linear optimization. This con
Let $V$ be a finite vector space over a finite field of order $q$ and of characteristic $p$. Let $Gleq GL(V)$ be a $p$-solvable completely reducible linear group. Then there exists a base for $G$ on $V$ of size at most $2$ unless $q leq 4$ in which c
In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph $G subseteq K_{n,n}$ has a perfect matching, together with an efficient algor