Have to find Boolean circuit formula that solves PARITYn problem with complexity O(n^2)?

(Function PARITYn(x1, . . . , xn) is equal to 1 if and only if the number of variables x1, . . . , xn equal to 1 is odd.)

  • 1
    $\begingroup$ What did you try? Where did you get stuck? What's the smallest circuit you've been able to design so far? Do you know how to compute the sum with a circuit of size $O(n^2)$? We're happy to help you understand the concepts but just solving exercise-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Feb 20 at 23:17
  • $\begingroup$ Use divide and conquer. $\endgroup$ – Yuval Filmus Feb 23 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.