The answers to both questions are known to be NO.

Analysis of Question 1:

A monotone Boolean function ( f ) in P can be computed by a polynomial-size (non-monotone) circuit, but this does not guarantee that ( f ) can be well-approximated by a polynomial-size monotone circuit. Consider the MATCHING function, which is monotone (adding edges cannot remove a perfect matching) and lies in...

Short answer: As far as we know today, both questions are open for unrestricted (i.e., arbitrary-depth) circuits. We do not know any explicit monotone function family in P/poly for which every monotone circuit that achieves even constant-bounded error under the uniform distribution (or at its critical p) must have superpolynomial size; conversely, we also do not have a general positive theorem sho...

Question 1 is about approximating any monotone Boolean function with a polynomial-size circuit by another monotone circuit of size q(n), such that they agree on most inputs. Question 2 is similar b...

Short answer

1. We do not know the answer when the function is required to lie in P.
2. If we drop the “ f∈P ” requirement the answer is already NO: there are explicit monotone Boolean functions for which every monotone circuit that agrees with the function on even a (1/2+δ)-fraction of the inputs must be super-polynomially large.

Below is a summary of what is and is not k...

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...

This is an excellent and deep question that touches on fundamental concepts in circuit complexity, approximation, and learning theory. The instinctive answer, as you note, is NO for both questions. This intuition is widely believed to be correct, although proving it unconditionally is likely as hard as proving major complexity class separations like P vs NP.

Let's break down the reasoning for...

Short answer – Nothing of the sort is known at the moment.
We do not have any explicit monotone function that is computable in polynomial time but that provably resists every polynomial–size monotone circuit even if the circuit is only required to agree with the function on, say, 51 % of the inputs. All the lower–bound techniques that give super-polynomial monotone-circuit lower bounds (Razborov...

This is a fascinating question about the approximability of monotone Boolean functions in P by polynomial-size monotone circuits. Let me analyze both questions:

Background and Context

The key tension here is between:

• General (non-monotone) polynomial-size circuits that can compute monotone functions
• Monotone polynomial-size circuits, which are more restricted

We know from Razborov's cele...

Monotone Boolean Functions Approximation in Circuit Complexity

This question explores the relationship between monotone Boolean functions in P and their approximability by monotone circuits. Let me address both questions and provide some context.

Current State of Knowledge

Both questions touch on fundamental issues in monotone circuit complexity, a challenging area in computational complex...