Prelegent: dr Maksim Barketau (National Academy of Sciences of Belarus, Belarus)
Miejsce: Sala seminaryjna B1-8
Data i godzina: 25 czerwca 2018 r., g. 12:00
Abstract: Product partition problems are the recognition problems that have a multiplicative operation in their formulation. First, we will recall the well-known NP-complete problem SUBSET PRODUCT and its properties. Next, we will formulate another problem of this type, PRODUCT PARTITION, and present the intuition behind the proof of its strong NP-completeness. Finally, we will consider the problem 3-PRODUCT PARTITION and give the sketch of the proof of its strong NP-completeness.