24
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 ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
Related Tags
black-box × 11cr.crypto-security × 4
quantum-computing × 3
cc.complexity-theory × 2
reference-request × 2
reductions × 2
oracles × 2
relativization × 2
ds.algorithms × 1
optimization × 1
circuit-complexity × 1
randomized-algorithms × 1
boolean-functions × 1
lg.learning × 1
communication-complexity × 1
quantum-information × 1
dc.parallel-comp × 1
permutations × 1
hash-function × 1
search-problem × 1
property-testing × 1
zero-knowledge × 1
metrics × 1