Geodesic
Decision problems for some classes of integer partitions and number multisets
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XVIII, Tome 378 (2010), pp. 171-183 
V. A. Shlyk. Decision problems for some classes of integer partitions and number multisets. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XVIII, Tome 378 (2010), pp. 171-183. http://geodesic.mathdoc.fr/item/ZNSL_2010_378_a10/
@article{ZNSL_2010_378_a10,
     author = {V. A. Shlyk},
     title = {Decision problems for some classes of integer partitions and number multisets},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {171--183},
     year = {2010},
     volume = {378},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2010_378_a10/}
}
TY  - JOUR
AU  - V. A. Shlyk
TI  - Decision problems for some classes of integer partitions and number multisets
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2010
SP  - 171
EP  - 183
VL  - 378
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2010_378_a10/
LA  - ru
ID  - ZNSL_2010_378_a10
ER  - 
%0 Journal Article
%A V. A. Shlyk
%T Decision problems for some classes of integer partitions and number multisets
%J Zapiski Nauchnykh Seminarov POMI
%D 2010
%P 171-183
%V 378
%U http://geodesic.mathdoc.fr/item/ZNSL_2010_378_a10/
%G ru
%F ZNSL_2010_378_a10

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

We show that the class of integer partitions that cannot be represented as convex combinations of two partitions of the same number coincides with the class of knapsack partitions and the class of Sidon multisets, which includes sum-free sets and standard Sidon sets. The decision problem for knapsack partitions is proved to be co-$NP$-complete, and, therefore, it cannot be solved in polynomial time unless $P=NP$. Bibl. 13 titles.

[1] M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[2] R. Rokafellar, Vypuklyi analiz, Mir, M., 1973

[3] U. Fulton, Tablitsy Yunga i ikh prilozheniya k teorii predstavlenii i geometrii, MTsNMO, M., 2006

[4] V. A. Shlyk, “O vershinakh politopov razbienii chisel”, Doklady NAN Belarusi, 52:3 (2008), 5–10 | MR | Zbl

[5] V. A. Shlyk, “Kombinatornye operatsii porozhdeniya vershin politopa razbienii chisel”, Doklady NAN Belarusi, 53:6 (2009), 27–32 | MR | Zbl

[6] V. A. Shlyk, “Kriterii predstavleniya razbienii chisel v vide vypukloi kombinatsii dvukh razbienii”, Vestn. BGU. Ser. 1, 2009, no. 2, 109–114 | MR | Zbl

[7] G. Endryus, Teoriya razbienii, Nauka, M., 1982 | MR

[8] N. Bohr, F. Kalckar, “On the transmutation of atomic nuclei by impact of material particles: I. General theoretical remarks”, Kgl. Danske Vid. Selsk. Skr., 14 (1937), 1–40

[9] L. Debnath, “Srinivasa Ramanujan (1887–1920) and the theory of partitions of numbers and statistical mechanics. A centennial tribute”, Internat. J. Math. Math. Sci., 10:4 (1987), 625–640 | DOI | MR | Zbl

[10] R. Ehrenborg, M. A. Readdy, “The Möbius function of partitions with restricted block sizes”, Adv. Appl. Math., 39:3 (2007), 283–292 | DOI | MR | Zbl

[11] V. A. Shlyk, “Polytopes of partitions of numbers”, European J. Combin., 26:8 (2005), 1139–1153 | DOI | MR | Zbl

[12] V. A. Shlyk, Recursive operations for generating vertices of integer partition polytopes, Communication of the Joint Institute for Nuclear Research E5-2008-18, Dubna, 2008

[13] T. Tao, V. H. Vu, Additive Combinatorics, Cambridge Univ. Press, Cambridge, 2006 | MR