k-DNF and Acyclic Extensions of pdBfs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F05%3A00000679" target="_blank" >RIV/00216208:11320/05:00000679 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

k-DNF and Acyclic Extensions of pdBfs

Original language description

The problem of finding an extension of a partially defined Boolean function (pdBf) is the problem of finding a Boolean function, which correctly classifies given data. That means that in general we are given two sets of Boolean vectors - truepoints and falsepoints - and we want to decide if there exists an extension - a Boolean function, that on all given truepoints has function value true and on all given falsepoints has function value false. In the case of positive answer we also want to find some representation of some extension. In our contribution we will show that it is NP-complete to decide whether there exists an acyclic extension for a given pdBf. We will also present a polynomial algorithm for finding a k-DNF extension (for fixed k) and provethat with respect to asymptotic time complexity it is the optimal procedure for solving this problem.

Czech name

k-DNF a acyklická rozšíření částečně definovaných booleovských funkcí

Czech description

Problémem hledání rozšíření částečně definované booleovské funkce rozumíme nalezení booleovské funkce, která správně ohodnocuje daná data. To znamená, že dostaneme dvě množiny booleovských vektorů určující, kde má částečně definovaná funkce hodnotu truea kde false. A naším úkolem je rozhodnout, zda existuje rozšíření, tedy totální booleovská funkce, která se na zadaných vektorech shoduje s částečně defnovanou booleovskou funkcí. V našem příspěvku ukážeme, že problém nalezení acyklického rozšíření danéčástečně definované funkce patří mezi NP-úplné problémy. Také představíme polynomiální algoritmus rozhodující, zda existuje k-DNF rozšíření (pro pevné k) a dokážeme, že jeho asymptotická časová složitost je optimální.

Type

D - Article in proceedings

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/GD201%2F05%2FH014" target="_blank" >GD201/05/H014: Collegium Informaticum</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2005

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

MIS 2005

ISBN

80-86732-70-3

ISSN

—

e-ISSN

—

Number of pages

11

Pages from-to

38-48

Publisher name

MFF

Place of publication

Praha

Event location

Praha

Event date

Jan 1, 2005

Type of event by nationality

CST - Celostátní akce

UT code for WoS article

—