Thus, from what we have stated, (A1) can be reducible to (A2), which implies (A2) is #P-hard.