18
The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to.
For example, suppose you have a 3-sat problem:
(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
(x2 ∨ x3 ∨ ¬x4) ∧
(x1 ∨ ¬x2 ∨ x4) ∧
(x1 ∨ x3 ∨ x4) ∧
(¬x1 ∨ x2 ∨ ¬x3)
Or, in table form with each row being a 3-clause, x meaning "this variable false", o ...
7
Actually, the problems BBB and BBB-F above are not currently specified as languages or decision problems (the black box is not explicitly given to us as a binary string of some kind, is it?), so these problem cannot be in NP, PP, PSPACE, or even decidable/undecidable. A fundamental property of languages in the computability/complexity sense is that no bit of ...
4
The work of Berman, Raskhodnikova, and Yaroslavtsev [1] introduces testing of functions $f\colon [n]^d\to \mathbb{R}$ with regard to $L_p$ distances, for $p\geq 1$. It is meant to capture situations where the magnitude of the noise is what matters (rather than the more brittle Hamming distance). (Some results pertaining to $L_p$ distances can also be found ...
3
Your problem is at least as hard as the NP-hard problem called Minimum Feedback Arc Set.
Consider a directed graph and set $f(u,v)=1$ if it contains an arc from $u$ to $v$, and $0$ otherwise. Then your problem corresponds to finding a minimum feedback arc set: a minimum set of arcs whose removal yields a directed acyclic graph (DAG). From such a DAG, one ...
2
Googling "learning boolean function problem" from M. Alaggan says that BBB and BBB-F is at most NP-Hard and you can optimize the problem for certain inputs.
Only top voted, non community-wiki answers of a minimum length are eligible
