The Library
Shrinkage of de Morgan formulae under restriction
Tools
Tools
Tools
Paterson, Michael S. and Zwick, Uri (1991) Shrinkage of de Morgan formulae under restriction. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-171.pdf - Other - Requires a PDF viewer. Download (4Mb) | Preview |
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 at least a factor of epsilon((5-sqrt(3))/2) ~= epsilon 1.63. (A de Morgan formula is a formula over the basis {/\, \/, ~}.) This improves a long-standing result of epsilon 1.5 by Subbotovskaya and a recent improvement to epsilon((21-sqrt(73))/8) ~= epsilon 1.55 by Nisan and Impagliazzo. The new exponent yields an increased lower bound of omega(n((7-sqrt(3))/2-O(1)) for the de Morgan formula size of a function defined by Andreev. This is the largest lower bound known for a function in NP.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Proposition (Logic) | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | January 1991 | ||||
| Dates: |
|
||||
| Number: | Number 171 | ||||
| Number of Pages: | 9 | ||||
| DOI: | CS-RR-171 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Publisher Statement: | M.S. Paterson and U. Zwick, “Shrinkage of de Morgan Formulae under Restriction”, <i>Random Structures and Algorithms</i> <b>4</b>, pp. 135-150 (1993) | ||||
| Funder: | European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
| Grant number: | 3075 (ESPRIT) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
