In short, the question is: to what extent, computational ability for hard tasks really helps you in solving easy tasks. (There could be various ways to make this question interesting and non-trivial, and here is one such attempt.)
Question 1:
Consider a circuit for solving SAT for a formula with n variables. (Or for finding Hamiltonian cycle for a graph with $n$ edges.)
Suppose that every gate allows the computation of an arbitrary Boolean function on $m$ variables. For concreteness let’s take $m=0.6 n$.
The Strong exponential time hypothesis (SETH) asserts that even with such strong gates we need superpolynomial circuit size. In fact, we need size at least $\Omega (2^{(0.4-\epsilon) n})$ for every $\epsilon.$ In a sense, gates on fraction of the variables that represent very complicated Boolean functions (much beyond NP-completeness) do not give you much advantage.
We can further ask:
(i) Can we have such a circuit of size $2^{0.9 n}$? $2^{(1-\epsilon)n}$?
A “no” answer will be a vast strengthening of the SETH . Of course, maybe there is an easy “Yes” answer, that I simply miss.
(ii) If the answer to (i) is YES, do gates that computes arbitrary Boolean functions give some advantages compared to gates which “just” compute (say) arbitrary NP functions; or just smaller instances of SAT itself ?
The next question attempts to ask something similar for questions in $P$.
Question 2:
As before let $m< n$ and for concreteness put $m=0.6n$. (Other values of $m$ such as $m=n^\alpha$ are also of interest.) Consider the following types of circuits:
a) In one step you can compute an arbitrary Boolean function on $m$ variables.
b) In one step you can solve a SAT problems with $m$ variables. Or perhaps an arbitrary nondeterministic circuit of polynomial size in $m$ variables.
c) In one step you can perform an arbitrary circuit on $m$ variables of size $m^d$ ($d$ is fixed).
d) In one step you can perform ordinary Boolean gates.
Let us consider the question of finding a perfect matching for a graph with $n$ edges. Matching has a polynomial size circuit. The question is if the exponent in such a matching algorithm can be improved when you move from circuits of type d) to circuits of type c), and from circuits of size c) to circuits of size b), and from circuits of size b) to circuits of size a).
(This may be related to well-known issues about parallel computation or about oracles.)
