patternMinor
Complexity of black box satisfiablty
Viewed 0 times
satisfiabltyboxcomplexityblack
Problem
Say I have a black box $f : 2^n \to 2$ and I want to determine if it is satisfiable. That is, does there exist an input how which it returns true. I am for the purposes of this considering $n$ to be the size of the problem. Perhaps that is a bad assumption to make but it seems a reasonable assumption.
Clearly I can reduce SAT to this problem but can I efficiently reduce this problem to SAT? I couldn't think of an efficient way and it doesn't seem possible due to the black box nature. It clearly lies in EXPTIME because I could just try each input. Further still it lies in PSPACE because the I only need to enumerate the linear space assignments. It does not however appear to be in NP as far as I can tell. I can't seem to figure out if it lies in PH either.
Has the complexity of this problem been studied? If so what complexity class does it lie in?
Clearly I can reduce SAT to this problem but can I efficiently reduce this problem to SAT? I couldn't think of an efficient way and it doesn't seem possible due to the black box nature. It clearly lies in EXPTIME because I could just try each input. Further still it lies in PSPACE because the I only need to enumerate the linear space assignments. It does not however appear to be in NP as far as I can tell. I can't seem to figure out if it lies in PH either.
Has the complexity of this problem been studied? If so what complexity class does it lie in?
Solution
If it's a black box, you can't reduce it to SAT. That's exactly what it means to be a black box: a black box is one where you can feed in any input $x$ you like, and get back $f(x)$, but where you know nothing about the structure of $f$ (for instance, you are not given an algorithm for $f$, you do not know the CNF for $f$, and so forth).
In particular, given only black-box access to $f$, in the worst case, you need $2^n$ queries to the black box to determine whether $f$ is satisfiable: you need to evaluate $f$ on every possible input, in the worst case. Consider any algorithm which makes at most $2^n-1$ queries to the black box. Suppose it got back $0$ as the answer to every query. Then there is some input, say $x'$, which has not been queried. Now the correct answer as to whether $f$ is satisfiable depends upon whether $f(x')=0$ or $f(x')=1$, but the algorithm has no clue which is the case. No matter what the algorithm outputs, an adversary could always pick a $f$ (after the fact) that is consistent with all of the queries made to the black box but that makes the algorithm's output wrong. Therefore, no deterministic algorithm can do better than $2^n$ queries, in the worst case.
It's not in EXPTIME, and it's not in NP, because it is an oracle problem, whereas NP and EXPTIME are for non-oracle problems -- but it is in the analogue of EXPTIME for oracle problems.... and in the analogue of NP for oracle problems, too.
In particular, given only black-box access to $f$, in the worst case, you need $2^n$ queries to the black box to determine whether $f$ is satisfiable: you need to evaluate $f$ on every possible input, in the worst case. Consider any algorithm which makes at most $2^n-1$ queries to the black box. Suppose it got back $0$ as the answer to every query. Then there is some input, say $x'$, which has not been queried. Now the correct answer as to whether $f$ is satisfiable depends upon whether $f(x')=0$ or $f(x')=1$, but the algorithm has no clue which is the case. No matter what the algorithm outputs, an adversary could always pick a $f$ (after the fact) that is consistent with all of the queries made to the black box but that makes the algorithm's output wrong. Therefore, no deterministic algorithm can do better than $2^n$ queries, in the worst case.
It's not in EXPTIME, and it's not in NP, because it is an oracle problem, whereas NP and EXPTIME are for non-oracle problems -- but it is in the analogue of EXPTIME for oracle problems.... and in the analogue of NP for oracle problems, too.
Context
StackExchange Computer Science Q#45157, answer score: 4
Revisions (0)
No revisions yet.