There is an oracle built around a hidden $m\times n$ matrix $A$ all of whose entries are 0 or 1, where $m>n$. The oracle takes as input an integer vector $b$ with positive entries, and answers as follows:
- The oracle answers YES, if there exists a real vector $x$ with $Ax=b$.
- The oracle answers NO, if no such real vector $x$ exists.
It is furthermore known that there exists some YES-vector $b$, whose entries are all bounded by the known (explicitly given) constant $c$.
Question: What conditions on $A$ would enable us to find a YES-vector $b$ in polynomial time?
I'm actually working on a slightly different problem, and the context is a bit hard to explain: in my problem matrix $A$ represents an incidence matrix for a minimum edge clique cover of a graph $G$. Each column of $A$ is a (maximal) clique in $G$, with a $1$ in entry $i,j$ if vertex $i$ is in clique $j$. Ideally, such an $A$ would satisfy the problem statement.
I am interested in deterministic algorithms, not a randomized algorithm.
I was wondering which search terms I should put into Google, and what type of literature exists on this problem.