Mechanical linkage design and NP-hardness

Abstract We prove the NP-hardness of two fundamental problems in mechanism design. Given a set of rigid parts and prescribed joints, the first problem consists in deciding whether there exists an assembly of these parts matching the link constraints. Given a set of rigid parts and prescribed joints with parameterized dimensions, the second problem consists in deciding if there exists some dimensioning making the assembly mobile. The proof of hardness makes use of a reduction from Partition Problem for the first problem and from 3SAT for the second one.