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.

I'm working through the problems in Arora & Barak's textbook on Computational Complexity. It's all been good so far, but I'm kind of stuck on this pair of problems in Chapter 2 (2.3 and 2.4). I'm worried that it needs more linear algebra than I know, and the hint in the back of the book only confuses me more. Any pointers in the right direction would be appreciated.

Problem 2.3: Let $LINEQ$ denote the set of satsifiable rational linear equations. That is, LINEQ consists of the set of all pairs $\langle A,b \rangle$ where $A$ is an $m*n$ rational matrix and $b$ is an $m$-dimensional rational vector, such that $Ax=b$ for some $n$-dimensional vector $x$. Prove that $LINEQ$ is in $NP$ (the key is to prove that if there exists such a vector $x$, then > there exists an $x$ whose coefficients can be represented using a number of bits that is polynomial in the representation of $A,b$). (Note that $LINEQ$ is actually in $P$: Can you show this?)

My current answer to the above is that the problem is in P via Gaussian elimination. It seems like there's better way, which I'd like to know, but I'm ok with leaving my answer like this. The hint in the back says to show that the determinant of a rational matrix uses a number of bits polynomial in the matrix's representation (simple enough) and then use Cramer's rule. But Cramer's rule only applies to square matrices, if I understand correctly, whereas the exercise is more general. What am I missing?

Problem 2.4 Show that the 'Linear Programming' problem in NP: Given a list of $m$ linear inequalities with rational coefficients over $n$ variables $u_1...u_n$ (a linear inequality has the form $a_1*u_1 + ... + a_n*u_n \le b$ for some coefficients $a_1...a_n, b$), decide if there is an assignment of rational numbers to the variables $u_1...u_n$ that satisfies all the inequalities. The certificate is the assignment.

Basically, $Ax \le b$. Again, the point seems to be showing that the solution vector uses a a polynomial number of bits. Which seems intuitive, but I'm stuck on proving it. The hint says to use the previous problem (2.3). Tried to come up with a kind of argument by contradiction, but can't get around certain cases.

share|improve this question
1  
If $Ax=b$ has a solution then it has a solution supported on a basis of the columns of $A$, so $x_i=0$ if the $i$-th column of $A$ is not in the basis. Now the entries of $x$ are given by Cramer's rule. –  Chris Godsil Oct 5 '11 at 19:35

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.