Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose $P$ is a polyhedron whose representation as a system of linear inequalities is given to us: $$ P = \{ x ~|~ Ax \leq b\}$$ Define $P'$ be the image of $P$ under the linear transformation which maps $x$ to $Cx$:
$$ P' = \{ Cx ~|~ x \in P \}.$$ Given $A,b,C$, our goal is to compute a representation of $P'$ as a system of linear inequalities, i.e., to compute $D,e$ satisfying $$ P' = \{ x ~|~ D x \leq e \}.$$ What is the complexity of this problem (i.e., how many arithmetic operations or bit operations are required)?

Let us adopt the convention that $A \in R^{m \times n}$ while $C \in R^{k \times n}$ so the answer should be in terms of $m,n,k$. Further, one may suppose that entries of $P$ are rational numbers whose numerators and denominators take $B$ bits to specify, so that in the bit-model answers should be in terms of $B$ as well.

share|improve this question
    
Perhaps you should add something on why you expect this not to be simply the complexity of computing $D=AC^{-1}$ (assuming $C$ is invertible). –  joriki Aug 25 '12 at 8:00
add comment

1 Answer

I think the common approach is to use quantifier elimination. The image $P'$ is defined by the formula $$ \exists x. Ax \leq b \land x' = Cx $$ By eliminating the quantifiers for the $x$-variables, you get a system of inequalities on the variables $x'$ that define the resulting polyhedron $P'$.

Quantifier elimination for linear arithmetic can be done by Ferrante and Rackoff's method [1, Chapter 7.3]. The complexity of this method is $2^{2^{pn}}$ for a formula of length $n$ and some fixed constant $p$ [1, Theorem 2.24].

[1] Bradley, A.R., Manna, Z.: The Calculus of Computation: Decision Procedures with Applications to Verification. Springer, Heidelberg (2007)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.