The Library
SHRINKAGE OF DE MORGAN FORMULAS UNDER RESTRICTION
Tools
UNSPECIFIED (1993) SHRINKAGE OF DE MORGAN FORMULAS UNDER RESTRICTION. RANDOM STRUCTURES & ALGORITHMS, 4 (2). pp. 135-150. ISSN 1042-9832.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
It is shown that a random restriction leaving only a fraction epsilon of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor of O(epsilon(5-square-root 2)/2) = O(epsilon1.63). (A de Morgan, or unate, formula is a formula over the basis {AND, OR, inverted left perpendicular}.) This improves a long-standing result of O(epsilon1.5) by Subbotovskaya and a recent improvement to O(epsilon(21-square-root 73)/8) = O(epsilon 1.5) by Nisan and Impagliazzo. The new exponent yields an increased lower bound of n(7-square-root 3)/2-o(1) = OMEGA(n2.63) for the de Morgan formula size of a function in P defined by Andreev. This is the largest formula size lower bound known, even for functions in NP.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | RANDOM STRUCTURES & ALGORITHMS | ||||
Publisher: | JOHN WILEY & SONS LTD | ||||
ISSN: | 1042-9832 | ||||
Official Date: | 1993 | ||||
Dates: |
|
||||
Volume: | 4 | ||||
Number: | 2 | ||||
Number of Pages: | 16 | ||||
Page Range: | pp. 135-150 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |