3
$\begingroup$

After discussing in the comments, I think a clearer definition of the question is as follows: for a random function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, what is the probability that there exists a non-injective function $g : \{0, 1\}^n \rightarrow \{0, 1\}^m$ defined by $m$ conjunctions on $2$ variables, with arbitrary negations, such that $\forall x, y \in \{0, 1\}^n, g(x) = g(y) \Rightarrow f(x) = f(y)$ with $g$?

Here is the former description for context:

Here, consider circuits to have $AND$ and $OR$ gates with fan-in $2$, with negations optionally present at any input to a gate, and to be alternating and synchronous (Harper 1977), the latter meaning that there are layers such that layer $1$ only accesses the inputs, layer $2$ only accesses layer $1$, and so on, and the former meaning that each layer has exclusively $AND$s or $OR$s, which one alternating layer by layer. For any function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, we can then consider an arbitrary circuit $C$ which computes it, and "chop off" everything above the first layer. Doing so, if that layer had $w$ gates (width $w$), we get new, multi-output circuit which computes a function $g_C : \{0, 1\}^n \rightarrow \{0, 1\}^w$.

My question is: for uniformly random $f$, what is the probability that there exists such a $C$ which compute $f$ such that $g_C$ is not injective?

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ Your description of the circuit model appears incomplete. As written, the circuits are monotone, hence a random Boolean function cannot be computed in this model at all, with overwhelming probability. $\endgroup$
    – Emil Jeřábek
    Commented Nov 18, 2021 at 8:51
  • $\begingroup$ I made it explicit, though maybe there is a way to more concisely state it with a common name for the basis with ANDs, ORs with arbitrary negations? $\endgroup$
    – Samuel Schlesinger
    Commented Nov 18, 2021 at 18:58
  • $\begingroup$ If you have negations for free anywhere, then what’s the point of making the layers alternating? You can turn any AND into an OR by negating all its input and output wires, and vice versa. $\endgroup$
    – Emil Jeřábek
    Commented Nov 18, 2021 at 19:04
  • $\begingroup$ Yes, good point. Is the typical way to push the negations to the bottom and make it alternating? $\endgroup$
    – Samuel Schlesinger
    Commented Nov 18, 2021 at 19:05
  • 1
    $\begingroup$ I just care about the existence of $m$ width 2 conjunctions (possibly containing negations) computing a non-injective function $g : \{0, 1\}^n \rightarrow \{0, 1\}^m$ such that $\forall x, y, g(x) = g(y) \Rightarrow f(x) = f(y)$. $\endgroup$
    – Samuel Schlesinger
    Commented Nov 18, 2021 at 19:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.