Markus Lohrey выступит на следующем семинаре Омского филиала МЦА

15 октября в 19:00 по новосибирскому времени (18:00 по омскому времени, 15:00 по московскому) пройдёт семинар №204. С докладом «Knapsack and the power word problem in solvable Baumslag-Solitar groups» выступит Markus Lohrey (Siegen University, Germany). На последующих семинарах выступят A. Miasnikov, V. Remeslennikov, A. Treyer. 

We show that the power word problem for a solvable Baumslag-Solitar groups BS(1,q) belongs to the circuit complexity class TC0; a very small complexity class within polynomial time (even logspace). The power word problem is a succinct version of the classical word problem, where the input consists of group elements g_1,…, g_d (encoded as words over a set of generators) and binary encoded integers z_1,..., z_d and it is asked whether g_1^{n_1} ... g_d^{n_d} = 1 holds in the underlying group. Moreover, we prove that the knapsack problem for BS(1,q) is NP-complete. In  the knapsack problem, the input consists of group elements g_1,…, g_d, h, and it is asked whether the equation g_1^{x_1} ... g_d^{x_d} = h  (where the x_i are variables ranging over the natural numbers) has a solution.

Чтобы присоединиться к семинару, за несколько минут до начала присоединитесь к конференции Zoom по ссылке https://us02web.zoom.us/wc/join/81220793393 или вручную, введя номер конференции 812 2079 3393 в приложении Zoom.

Обратите, пожалуйста, внимание на следующие правила проведения интернет семинара:
  • Желательно входить под своим именем и фамилией
  • На время доклада просьба отключить микрофон
  • Для удобства докладчика рекомендуется размещать вопросы заранее в чате