This article is cited in 1 paper

A lower bound for the complexity of inclusive search in the class of tree-like circuits

È. È. Gasanov


Abstract: In the class of tree information networks with a base set of variables we give examples of inclusive search problems such that the order of magnitude of lower bounds for their complexity exceeds the average time of solution output.
This research was supported by the Russian Foundation for Basic Research, grant 95–01–00597.

UDC: 519.7

Received: 13.10.1997

DOI: 10.4213/dm412

 English version: Discrete Mathematics and Applications, 1998, 8:1, 99–108

Bibliographic databases:

• 
•