✦ LIBER ✦

The Minimum Equivalent DNF Problem and Shortest Implicants

✍ Scribed by Christopher Umans

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 149 KB
Volume: 63
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.2001.1775

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that the Minimum Equivalent DNF problem is S P 2 -complete, resolving a conjecture due to Stockmeyer. We also consider the complexity and approximability of a related optimization problem in the second level of the polynomial hierarchy, that of finding shortest implicants of a Boolean function. We show that when the input is given as a DNF, this problem is complete for a complexity class above coNP utilizing O(log 2 n)-limited nondeterminism. When the input is given as a formula or circuit, the problem is S P 2 -complete, and S P

📜 SIMILAR VOLUMES

Equivalence between the minimum covering

Equivalence between the minimum covering problem and the maximum matching problem

✍ Ján Plesník 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 127 KB

The minimum covering problem in weighted graphs with n vertices is transformed in time O(n 2) to the maximum matching problem with n or n + 1 vertices, and conversely.

An efficiently solvable case of the mini

An efficiently solvable case of the minimum weight equivalent subgraph problem

✍ M. B. Richey; R. Gary Parker; R. L. Rardin 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB

The shortest and the K-shortest routes a

The shortest and the K-shortest routes as assignment problems

✍ A. Weintraub 📂 Article 📅 1973 🏛 John Wiley and Sons 🌐 English ⚖ 552 KB

## Abstract The problem of finding a shortest route in a network with unrestricted costs is approached through solving an assignment problem associated to the network. The upper bound on the number of elementary calculations required for the solution is 0(m^3^). However, in most cases, the actual

The constrained shortest path problem

✍ Y. P. Aneja; K. P. K. Nair 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB

Inapproximability results for the invers

Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths

✍ Andreas Bley 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB

## Abstract We study the complexity of two inverse shortest paths (ISP) problems with integer arc lengths and the requirement for uniquely determined shortest paths. Given a collection of paths in a directed graph __D__ = (__V__, __A__), the task is to find positive integer arc lengths such that th

On the minimum vocabulary problem

✍ Chandrasekharan, N. ;Sridhar, R. ;Iyengar, S.S. 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 557 KB

The "minimum vocabulary problem" for a dictionary has applications in indexing and other domains of information retrieval. A simple directed-graph model of a dictionary results in a linear-time algorithm for this problem. Since it is known that many minimum vocabularies can exist for a dictionary, a