Complexity of optimization on independence systems

Complexity of optimization on independence systems

0.00 Avg rating0 Votes
Article ID: iaor1990618
Country: United States
Volume: 37
Start Page Number: 1
End Page Number: 7
Publication Date: Mar 1988
Journal: Soviet Mathematics Doklady
Authors:
Abstract:

This note solves the problem of partial deciphering of monotone Boolean functions in the Shannon formulation, presents an easily realizable deciphering algorithm, and proves that it is optimal in the Shannon sense. It uses the present results to investigate the set of solutions and determine the complexity of the problem of optimization on independence systems.

Reviews

Required fields are marked *. Your email address will not be published.