Home / Events / Seminar: "TCP no implica DTCP" (E. Ventura, UPC)

Seminar: "TCP no implica DTCP" (E. Ventura, UPC)

Date: Wednesday November 6th, 13:10-14:10
Place: CRM, room C1/028
Títle: "TCP no implica DTCP".
Speaker: Enric Ventura, UPC.

Abstract: Definirem els següents problemes algorísmics en grups: WP, CP, TCP, DTCP, PCP, GPCP i HWP. És ben sabut que DTCP implica TCP implica CP implica WP. I els recíprocs són falsos: repassarem construccions clàssiques d'exemples on WP no implica CP, i una construcció de fa uns anys d'un grup amb CP resoluble i TCP irresoluble. Finalment, passant pel Post Correspondence Problem (PCP), una versió generalitzada (GPCP), i l'Hereditary Word Problem (HWP) veurem una demostració recent de Miasnikov-Nikolaev-Ushakov del fet que el grup lliure de rang 32 (i superior) té DTCP irresoluble, aportant així el primer grup conegut on TCP és resoluble i DTCP irresoluble. 
Filed under: , ,