6
$\begingroup$

It is pretty well taught that any binary function can be represented using CNF. But conversion to CNF can take an exponential number of gates. The truth table is exponentially sized relative to the number of input variables.

Is there any form of representing truth tables that requires only a polynomial or quasipolynomial number of gates? I know there are ones that preserve satisfiability, not equality---but is there anything that preserves equality?

$\endgroup$
2
  • $\begingroup$ What exactly is the input form of your "binary function"? $\endgroup$
    – Bergi
    Nov 3, 2023 at 18:52
  • $\begingroup$ Are you asking for a canonical form where you can compare the equality of functions in linear time (wrt the size of that form)? $\endgroup$
    – Bergi
    Nov 3, 2023 at 18:54

1 Answer 1

13
$\begingroup$

No. No matter what representation of functions as circuits/formulas you use, there will exist some functions that require exponential size to represent. This was proven by Shannon in 1949. See Shannon's result that some Boolean functions require exponential circuits.

Intuitively, you can count the number of circuits/formulas of polynomial size, and it is much less than the number of functions.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.