2012/12/14 by Balder ten Cate, Cate, Balder ten, Víctor Dalmau +1
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #cs.DM #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1212.3534
arxiv created 2012/12/14 · openalex publication_date 2012/12/14 · arxiv updated 2012/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The product homomorphism problem (PHP) takes as input a finite collection of relational structures A1, ..., An and another relational structure B, all over the same schema, and asks whether there is a homomorphism from the direct product A1 x ... x An to B. This problem is clearly solvable in non-deterministic exponential time. It follows from results in [1] that the problem is NExpTime-complete. The proof, based on a reduction from an exponential tiling problem, uses structures of bounded domain size but with relations of unbounded arity. In this note, we provide a self-contained proof of NExpTime-hardness of PHP, and we show that it holds already for directed graphs, as well as for structures of bounded arity with a bounded domain size (but without a bound on the number of relations). We also present an application to the CQ-definability problem (also known as the PP-definability problem). [1] Ross Willard. Testing expressibility is hard. In David Cohen, editor, CP, volume 6308 of Lecture Notes in Computer Science, pages 9-23. Springer, 2010.