1
$\begingroup$

Not having received a satisfactory response to this question in math.SE, I am asking it here:

In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-monotone circuits that are smaller than monotone circuits for Clique. I’m looking for a reference to these best-known circuits. I would also welcome a sketch of how they work.

Improve this question
$\endgroup$
3
  • $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. Please pick one site where you'd like the question to appear. If you posted it on the wrong site, you can delete the copy on the wrong site before posting it on the other site. $\endgroup$
    – D.W. ♦
    Commented Feb 1, 2019 at 1:26
  • $\begingroup$ I'm voting to close this question because it was cross-posted. $\endgroup$
    – D.W. ♦
    Commented Feb 1, 2019 at 1:26
  • 1
    $\begingroup$ @D.W. I think here the meaning is clear: the smallest circuits solving clique which are known. $\endgroup$
    – Yuval Filmus
    Commented Feb 1, 2019 at 6:28

0

Reset to default