Computing any information about Max-3SAT For a 3CNF formula $C$ let $M(C)$ be the maximal number of satisfied clauses in any assignment to $C$. It is known that Max-3SAT is hard to approximate (subject to P≠NP), i.e. there is no polytime algorithm whose input is a 3CNF formula $C$, and whose output is the number $M&#39;$ such that $M(C)$ is within a multiplicative factor $1+c$ from $M&#39;$, where $c&gt;0$ is an absolute positive constant.

I believe that it is also NP-hard to compute $M(C) \bmod p$ for any constant modulus $p$. I wonder if the following common generalization of these two facts is true: There is no polytime algorithm whose input is a 3CNF formula $C$ with $N$ clauses, and a string of $\log_2 N-B$ advice bits, and whose output is $M(C)$. Here $B$ is an absolute constant. In plain words, there is no algorithm that computes $B$ bits of information of $M(C)$. 

I apologize if the question has a well-known answer, for I am not a complexity theorist by the way of background.
Here is an argument that if you could solve Max 3SAT on an m-clause instance given a constant number of bits of advice, then the polynomial hierarchy would collapse.

Fix an NP-complete problem L. From Cook's theorem, we know a transformation f() of inputs x for L into 3SAT formulas f(x), so that

1) if $x\in L$ then $M(f(x)) = m$

2) if $x\in L$ then $M(f(x)) = m-1$

where $m$ is the number of clauses in $f(x)$.

We also have a theorem of Kadin, that says that, if given $k$ inputs $x_1,\ldots,x_k$ of an NP-complete problem, you have a polynomial time algorithm that makes $\leq k-1$ queries to an NP oracle and determines the correct answer to the $k$ NP problems $x_i \in ? L$, then the polynomial hierarchy collapses.

Suppose we have an algorithm that solves Max SAT on m-clause inputs given k bits of advice. We will use Hastad's result to construct an algorithm as in the premise of Kadin's theorem.

Start from the $K=2^k+1$ inputs $x_1,\ldots,x_K$ to problem $L$. Apply Cook's theorem to each of them. After some normalization (which can be done by assigning weights to the clauses, or duplicating them if we do not want to use weights), we construct $K$ formulas $F_1,\ldots,F_K$ where, for a certain $m$:

1) $M(F_1)= m-1$ if $x_1 \in L$ and $M(F_1) = m-2$ otherwise

2) $M(F_2) = m\cdot (m-1)$ if $x_2 \in L$ and $M(F_2) = m\cdot (m-2)$ otherwise

...

k) $M(F_K) = m^{K-1} \cdot (m-1)$ if $x_K\in L$ and $M(F_K) = m^{K-1} \cdot (m-2)$ otherwise

Now take the union of the formulas, which were constructed over disjoint variables sets, and call it $F$. So we have $M(F) = M(F_1) + \cdots + M(F_k)$, and we can "read off" the answer to the $K$ problems $x_i \in? L$ by looking at the base-$m$ representation of $M(F)$. If we can compute $M(F)$ given $k$ bits of advice, it means that we can find $2^k$ values such that one of them is $M(F)$. We can then ask non-adaptively an NP oracle whether $M(F) \geq n_i$ for each of the candidate values $n_1,\ldots,n_{2^k}$ we generated. So we have been able to solve $2^k+1$ instances of NP-complete problems by making $2^k$ non-adaptive queries to an NP oracle, which implies that the polynomial hierarchy collapses.

Using Hastad's theorem instead of Cook's theorem, it's possible to push  the size of $F$ to $O(1)^k \cdot m$ instead of $m^k$, so it's possible to push $k$ to $\log m$, and the number of advice bits to $\log\log m$. Understanding what happens when you are given  $\log m  - O(1)$ advice bits seems really difficult.



Edited to add: Krentel (The Complexity of Optimization Problems. J. Comput. Syst. Sci. 36(3): 490-509 (1988)) proved that computing the value of the optimum of the maximum clique problem is complete for $FP^{NP[O(log n)]}$, the class of functions computable in polynomial time with $O(log n)$ queries to an NP oracle. The completeness is under "one query reductions," in which function f is reducible to function g if one can write $f(x) = r_1(g(r_2(x))$ for polynomial time computable $r_1$ and $r_2$. Presumably the same is true for Max Clique. Now, if Max Clique had a polynomial time algorithm that produces a list of $m^{o(1)}$ possible values, it would be in $FP^{NP[o(logn)]}$, because you could use binary search to find the optimum with a number of queries that is log of the list size. 

Now, if we have $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$ we would definitely have $P^{NP[O(log n)]} = P^{NP[o(log n)]}$, which is the special case for decision problems, and that is known, by results of Wagner (improving a result of Kadin that applies to a constant number of queries), to collapse the polynomial hierarchy. But I think that it might be known that $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$  would actually imply P=NP. But in any case the results of Krentel and Kadin-Wagner should be enough to give another proof of Andy Drucker's result. Now I wonder if it is actually the same proof, that is, if the Fortnow-Van Melkebeek result works, explicitly or implicitly, via a "simulating NP queries with fewer NP queries" argument.

A good survey paper that explains what is going on with optimization problems and bounded query classes:

http://www.csee.umbc.edu/~chang/papers/bqabh/npfsat.pdf