|
COMMENT
|
A Krom function is equivalent to a Boolean function with the property that, if f(x)=f(y)=f(z)=1, then f(<xyz>)=1, where <xyz> denotes the bitwise median of the three Boolean vectors x, y, z.
Also related to number of retracts of an n-cube (see Feder).
|
|
REFERENCES
|
Tomas Feder, Stable Networks and Product Graphs, Memoirs of the American Mathematical Society, 555 (1995), Section 3.2.
D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.1 (in preparation).
M. R. Krom, The decision problem for a class of first-order formulas in which all disjunctions are binary, Zeitschrift f. mathematische Logik und Grundlagen der Mathematik, 13 (1967), 15-20.
Thomas J. Schaefer, The complexity of satisfiability problems, ACM Symposium on Theory of Computing, 10 (1978), 216-226.
|
