Algorithm 1 S

This section introduces the algorithmic construction of gadget circuits that will be adopted in our proofs of tractability as well as hardness. A construction algorithm for the support circuit is provided in Alg. 1. This construction is summarized in Alg. 2. It is a key component in the algorithms for many tractable We define a circuit representation of the #3SA T problem, following the construction in Khosravi et al. This section formally presents the tractability and hardness results w.r.t. The hardness of the sum of two circuits to yield a deterministic circuit has been proven by Shen et al.