Below is a brief summary of what is known (and not known) about these two approximation‐by‐monotone‐circuits questions.

1) Uniform‐measure approximation (Question 1)
—————————————————
We ask:
“Given any monotone f on n bits computable by some (possibly non‐monotone) size-p(n) circuit, and any fixed ε>0, can one always find a monotone size-q(n) circuit g that agrees with f on at least 1–ε of the 2ⁿ inputs?”

Status: Open.

■ No general positive “compiler” is known that turns arbitrary polynomial‐size circuits for a monotone f into monotone circuits of only polynomial blow-up that approximate f on almost all inputs.

■ Almost all the “case studies” we do have are ad hoc. For example:
– Threshold (majority) functions. Ajtai–Komlós showed that the majority function can be ε-approximated by depth-3 monotone circuits of size poly(n,1/ε). In fact one builds an “approximate majority” monotone circuit of size O(n ⋅ polylog(n/ε)).
– Perfect-matching. Razborov’s lower bound shows that exactly testing “does G have a perfect matching?” requires super-polynomial monotone size. But if we switch to ε-approximation under the critical probability (see Q2 below) one can approximate matching very well by the simple monotone test “G has no isolated vertex.” Under the Er­dös–Rényi threshold for matchings the probability that there is no matching but also no isolated vertex goes to zero.
– Connectivity. Similar remarks apply: exact monotone‐circuit size is super‐polynomial, but at the connectivity threshold one can approximate it by “no isolated vertex” or “no small cut” tests.

But beyond these special graph‐property examples and the threshold/majority case there is no theorem that every monotone‐P function has a polynomial-size ε-approximate monotone circuit.

2) Approximation at the critical bias p₍c₎ (Question 2)
————————————————————
Here one lets p = p_c(f) be the unique bias at which f(x)=1 with probability 1/2, and asks for approximation in the Bernoulli‐p measure:
“Can every monotone f in P be ε-approximated (under μₚ) by a monotone size-q(n) circuit?”

Again: Open.

■ The ad-hoc approximation of matching or connectivity by simpler monotone tests shows that for some specific graph properties we do have very small approximate circuits in the critical window.

■ But there is no general mechanism that, given any monotone-P function f, constructs a small monotone circuit g with μₚ[f≠g]≤ε.

Partial results and barriers
———————————
• Friedgut’s Junta theorem tells us that any Boolean f at bias p with total influence I can be ε-approximated (under μₚ) by a function of about exp(O(I/ε)) variables. Unfortunately for many monotone‐P functions the total influence at the critical point can be poly(n) or larger, so this does not yield a poly(n)-sized monotone circuit in general.

• DNF‐approximation (e.g. by truncating to width O(log(p-size/ε))) shows that if f has a small monotone DNF then one can ε-approximate it by a small DNF. But most P‐computable monotone functions do not come with small DNFs in the first place.

• On the negative side, no explicit monotone function in P is known to require super-polynomial size even for approximate monotone circuits under uniform or critical distributions. In particular, we do not yet have any lower bounds that rule out a positive answer to Q1 or Q2.

In fact this question is often singled out as the major open problem in the theory of monotone vs. non-monotone computation: can one recover most of P (up to ε-errors) inside monotone‐P at only polynomial overhead? Despite a number of clever special-case constructions (approximate majority, graph thresholds, etc.) and deep lower–bound techniques for the exact monotone model (Razborov, Alon–Boppana, etc.), no general positive or negative resolution is known.

References for further reading
——————————————————
– Razborov, “Lower bounds on monotone complexity of the matching function.”
– Ajtai–Komlós, “Nearly optimal depth-3 circuits for approximate majority.”
– Friedgut, “Boolean functions with low average sensitivity depend on few coordinates.”
– Gil Kalai’s blog post (2010) on noise stability and threshold circuits.

Bottom line: Both Question 1 and Question 2 remain open. It is widely believed the exact answers are “no,” but we have neither a general construction nor a general lower bound for approximate monotone complexity of P‐functions.