Assume we are given boolean formula or circuit (I don't know if answer for this scenarios is different, and I am interested in both). Can we in polynomial time say anything about corresponding function that can't be said by using truth table as an oracle?
Formally, for some polynomial $p$ let $X$ be set of boolean functions that are realizable with boolean formula of size $p(n)$, where $n$ is number of variables.
Say that $O \subseteq X$ is oracle-polynomial if there exists a polynomial algorithm with oracle that separates $O$ from $X \setminus O$. For example, set of functions that are zero on all-zeroes assignment is oracle-polynomial, while set of constant functions is not.
Say that $F \subseteq X$ is formula-polynomial if there exists a polynomial algorithm that takes boolean formula of size at most $p(n)$ and decides if this formula defines function from $F$.
Clearly, $O \subseteq F$, as we can use formula as truth table oracle. Is converse true - does $O = F$?
My thoughts:
If $P = NP$ then answer is no: checking if formula defines constant function is co-NP, thus if $P = NP$ then set of non-constant function is formula-polynomial, but not oracle-polynomial.
If we further restrict set of formulas, for example require input to be DNF, then answer is again "no" - set of functions that are $1$ on exactly one assignment will be formula-polynomial, but not oracle-polynomial.
If instead of boolean formulas we consider algorithms (and oracle answers if algorithm stops in $n$ steps with some output) without restriction on time - the answer is "yes" by Rice's theorem (as we can decide only trivial set of function, so having code of algorithm doesn't help).
No, the converse is not true.
Informally: Let $f$ be a formula that has a single satisfying assignment (it can be expressed with a formula of size $n$), and $g$ the always false formula. You can separate $f$ from $g$ based on looking at the formula, but it takes exponentially many oracle queries to separate $f$ from $g$. This result is unconditional (does not rely on the assumption that $P \ne NP$).
To be more precise/formal: let $\mathcal{F}$ be the set of formulas that are a conjunction of $n$ clauses, where the $i$th clause has either the form $x_i$ or $\neg x_i$. By construction, every formula in $f$ has a single satisfying assignment, and given the formula, it is easy to find the single satisfying assignment. Let $\mathcal{G}$ be the singleton set of a single formula, the always-false formula. An algorithm that can look at the formula can easily distinguish between $\mathcal{F}$ vs $\mathcal{G}$ (it is easy to recognize formulas in $\mathcal{F}$ or $\mathcal{G}$ from the formula itself). But it is hard for an algorithm that only has oracle access to distinguish between $\mathcal{F}$ vs $\mathcal{G}$. In particular, it takes exponentially many queries to distinguish between those two sets. (Why? Informally, because there are $2^n$ possible queries. For $\mathcal{F}$, all but one of those $2^n$ inputs returns false; for $\mathcal{G}$, all inputs return false. For $\mathcal{F}$, it takes exponentially many queries even to find a single query that returns true.)