In this thesis, we provide a new, improved tool for proving the intractability (under standard complexity-theoretic hypotheses) of the same broad class of properties of boolean circuits that the previous two results dealt with. In particular, we prove that any nontrivial counting property of boolean circuits is hard for FewP, the polynomial-ambiguity version of NP. Thus, we raise the ambiguity tolerated by the lower bound from constant to polynomial. Furthermore, we prove, via an oracle construction using the Party Lemma of Cai et al. [CGH+80], that the polynomial-ambiguity lower bound cannot, in terms of the exact type of hardness reduction used, be improved much using relativizable techniques.
This talk will present our contributions toward finding Rice-style theorems in complexity theory. It will show that our hardness result for polynomial-ambiguity nondeterminism is rather tight. It will also briefly mention the other proposed research sub-topics in the thesis, namely (a) self-witnessing languages and collective completeness for promise classes, (b) length-respecting Turing reductions and (c) optimal bound on the nonuniform complexity of semi-feasible sets.