Search: id:A109457
Results 1-1 of 1 results found.

%I A109457
%S A109457 2,4,16,166,4170,224716,24445368,5167757614,2061662323954
%N A109457 Number of Krom functions on n variables (or 2SAT instances): conjunctions 
               of clauses with two literals per clause.
%C A109457 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.
%C A109457 Also related to number of retracts of an n-cube (see Feder).
%D A109457 Tomas Feder, Stable Networks and Product Graphs, Memoirs of the American 
               Mathematical Society, 555 (1995), Section 3.2.
%D A109457 D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.1 (in 
               preparation).
%D A109457 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.
%D A109457 Thomas J. Schaefer, The complexity of satisfiability problems, ACM Symposium 
               on Theory of Computing, 10 (1978), 216-226.
%Y A109457 Cf. A109458, A109459, A102897.
%Y A109457 Cf. A112535.
%Y A109457 Sequence in context: A073924 A061588 A050472 this_sequence A105788 A071008 
               A001146
%Y A109457 Adjacent sequences: A109454 A109455 A109456 this_sequence A109458 A109459 
               A109460
%K A109457 nonn,hard
%O A109457 0,1
%A A109457 D. E. Knuth, Aug 24 2005

Search completed in 0.001 seconds