UNSPECIFIED (1993) SHRINKAGE OF DE MORGAN FORMULAS UNDER RESTRICTION. RANDOM STRUCTURES & ALGORITHMS, 4 (2). pp. 135-150. ISSN 1042-9832

Full text not available from this repository.

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
Date:	1993
Volume:	4
Number:	2
Number of Pages:	16
Page Range:	pp. 135-150
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/21472

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item