Skip to main content
5 votes

Relationship between size of Boolean functions and DFAs

Complementing the other answers, here are a few research papers that explicitly study the size of (one-way) DFAs that represent Boolean functions in the way the OP describes. Maximum and average state ...
Hermann Gruber's user avatar
5 votes

Relationship between size of Boolean functions and DFAs

Regarding question 3: There are $S^{2S} \cdot 2^S$ different DFAs on $S$ states (fixing the initial state), and so most Boolean functions require $\Omega(2^n/n)$ states. This is the same calculation ...
Yuval Filmus's user avatar
  • 14.5k
5 votes

Relationship between size of Boolean functions and DFAs

Here are are my attempts to answer. I'm not an expert on this subject. Please check all details for yourself. No. Consider $f$ defined by $f(x)=1$ iff $x_1 \ne x_{n/2+1}$ or $x_2 \ne x_{n/2+2}$ or ...
D.W.'s user avatar
  • 12.2k
4 votes
Accepted

Is there a generalized SAT problem for higher-order logics?

Yes, you may be interested in the paper "Higher-Order Quantified Boolean Satisfiability" by Chistikov, Haase, Hadizadeh, and Mansutti (https://doi.org/10.4230/LIPIcs.MFCS.2022.33)
Bartosz Bednarczyk's user avatar
2 votes
Accepted

Power of non-implicationally-complete Frege systems and Boolean equational calculus

$\let\eq\leftrightarrow\def\ru{\mathrel/}\let\ET\bigwedge$Frege systems are required to be implicationally complete to make all such systems p-equivalent, yielding a robust definition of the Frege ...
Emil Jeřábek's user avatar
1 vote
Accepted

Solve 3CNF in Poly-Time with Satisfiability Oracle

hint: assign values to variables one at a time and call algorithm A on resulting formula. if the result of algorithm A is satisfiable or non-satisfiable what does that mean about last variable ...
floating's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible