Extended Smolensky's method
DOI:
https://doi.org/10.7146/dpb.v19i315.6705Abstract
We give a simple extension of Smolensky's method by replacing Smolensky's concept of U^n_F-completeness by a new definition: F-hardness. An easy consequence of this definition is that F-hard functions do not have constant depth, polynomial size Boolean circuit with Mod_p, where p is the characteristic of F. By this extension, we can explicitly show many functions are hard, we establish a {\em Hardness Lemma} for a class of functions, and characterize when a function over a finite field is hard to compute by a small depth with Mod_p gates. Furthermore, we discuss the difficulties in extending Smolensky's theory over a general ring. While in general the nice relationship between the Boolean circuit model and the algebra of functions representing Boolean functions over a ring collapses, we can still extend the complexity theoretic notions introduced by this extended Smolensky's theory to a ring in order to classify functions over such a ring by their relative complexity. A result states that any representation of Majority over any ring R=Z/(r) for any fixed r in N is hard. This provides a kind of evidence that Majority is not AC^0 reducible to Mod_r.Downloads
Published
1990-07-01
How to Cite
Zhang, Z.-L. (1990). Extended Smolensky’s method. DAIMI Report Series, 19(315). https://doi.org/10.7146/dpb.v19i315.6705
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.