4
$\begingroup$

Denote by $\mathcal{M}(n)$ the set of all monotone functions $\{0,1\}^n \to \{0,1\}$.

Can $\mathcal{M}(n)$ be represented as $\mathcal{M}(n) = \{ f(t) | t\in \{0,1\}^k \}$ such that:

1) $k = \log |\mathcal{M}(n)| + O(n)$

2) $f \in DTIME(2^{O(n)})$ ?

(I mean that $f(i)$ is a truth table of a boolean function)

$\endgroup$

0

Your Answer

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