Using an oracle to find a vector $b$ for which $Ax=b$ has a solution

Question

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.

Answer 1

We can make one observation: adaptive access to the oracle doesn't help. You might as well fix in advance the set of queries you plan to make to the oracle. So, the condition is that there has to exist a polynomial-size set of candidate values of $b$, such that it is likely that at least one of those will work.

Why doesn't adaptive access help? That's because you can assume without loss of generality that every oracle query returns 0. In other words, given an adaptive algorithm for generating queries, run that algorithm with a fake oracle that always returns "no solution", record the list of queries it makes, and there's a list of candidate values of $b$ that a non-adaptive algorithm can use. This yields a non-adaptive algorithm that performs as well as the adaptive algorithm.

As a consequence, since you want a deterministic algorithm that always succeeds, a necessary and sufficient condition is that there must exist a polynomial-sized, polynomial-time-constructible set $B \subset \mathbb{Z}_{>0}^m$ such that for all possible matrices $A$ there exists at least one $b \in B$ that works for $A$ (i.e., such that there exists $x$ so that $Ax=b$).