|
| |
|
|
A000617
|
|
Number of NP-equivalence classes of threshold functions of n or fewer variables.
(Formerly M0727 N0272)
|
|
4
|
| |
|
|
|
OFFSET
|
0,1
|
|
|
COMMENTS
|
From Fabián Riquelme, Jun 01 2012: (Start)
NP-equivalence classes of threshold functions are equivalent to weighted games, in simple game theory.
The number for n=9 was first documented in the unpublished work:
N. Tautenhahn, Enumeration einfacher Spiele mit Anwendungen in der Stimmgewichtsverteilung, 2008. Master's thesis, University of Bayreuth, 269 pages (in German).
(End)
|
|
|
REFERENCES
|
S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38, Table 2.3.2. - Row 14.
S. Muroga, T. Tsuboi and C. R. Baugh, Enumeration of threshold functions of eight variables, IEEE Trans. Computers, 19 (1970), 818-825.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Table of n, a(n) for n=0..9.
S. Bolus, A QOBDD-based Approach to Simple Games, Dissertation, Doktor der Ingenieurwissenschaften der Technischen Fakultaet der Christian-Albrechts-Universitaet zu Kiel, 2012. - From N. J. A. Sloane, Dec 22 2012
I. Krohn, P. Sudhölter, Directed and weighted majority games, Math. Methods Operat. Res. 42 (2) (1995) 189-216, Table 1.
S. Kurz, On minimum sum representations for weighted voting games, arXiv:1103.1445v1 (2011).
S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971 [Annotated scans of a few pages]
S. Muroga, T. Tsuboi and C. R. Baugh, Enumeration of threshold functions of eight variables, IEEE Trans. Computers, 19 (1970), 818-825. [Annotated scanned copy]
Eda Uyanık, Olivier Sobrie, Vincent Mousseau, Marc Pirlot, Enumerating and categorizing positive Boolean functions separable by a k-additive capacity, Discrete Applied Mathematics, Vol. 229, 1 October 2017, p. 17-30. See Table 3.
|
|
|
CROSSREFS
|
Sequence in context: A336991 A223545 A088938 * A132183 A259878 A003504
Adjacent sequences: A000614 A000615 A000616 * A000618 A000619 A000620
|
|
|
KEYWORD
|
nonn,hard,more,nice
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
STATUS
|
approved
|
| |
|
|
