## Abstract

We consider the Stochastic Boolean Function Evaluation (SBFE) problem for classes of DNF formulas. The SBFE problem for DNF formulas is a “sequential testing” problem where we need to determine the value of DNF formula on an initially unknown input x = (x_{1}, ..., x_{n}), when there is a cost ci associated with obtaining the value of xi, each xi is equal to 1 with known probability p_{i}, and the x_{i} are independent. The goal is to minimize expected cost. The SBFE problem is inapproximable for general DNF formulas. We give approximate and exact algorithms for two subclasses of DNF formulas: monotone k-DNF and monotone k-term DNF. We also prove a lower bound result for evaluation of monotone CDNF formulas.

Original language | English (US) |
---|---|

State | Published - Jan 1 2014 |

Event | 2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014 - Fort Lauderdale, United States Duration: Jan 6 2014 → Jan 8 2014 |

### Conference

Conference | 2014 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014 |
---|---|

Country | United States |

City | Fort Lauderdale |

Period | 1/6/14 → 1/8/14 |

## ASJC Scopus subject areas

- Applied Mathematics
- Artificial Intelligence