Algebra Seminar talk
2024-11-22
Robin Sypniewski
Decidability of pp-interpretability
Abstract:
Given finite relational structures A and B, we prove that it is decidable whether A pp-interprets B. We give an upper bound for the computational complexity of this problem.