Mechanical linkage design and NP-hardness

• Algorithmic complexity applied to mechanism design
• 3SAT problem
• Partition problem
• Mounting an assembly from parts and relationships is a NP-hard problem.
• Dimensioning a mounted assembly in order to make it mobile is a NP-hard problem.

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.