A combinatorial min-max theorem and minimization of pure-Horn functions
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10335324" target="_blank" >RIV/00216208:11320/16:10335324 - isvavai.cz</a>
Result on the web
<a href="http://isaim2016.cs.virginia.edu/papers/ISAIM2016_Boolean_Boros_etal.pdf" target="_blank" >http://isaim2016.cs.virginia.edu/papers/ISAIM2016_Boolean_Boros_etal.pdf</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A combinatorial min-max theorem and minimization of pure-Horn functions
Original language description
A Boolean function of n variables is a mapping from {0;1}^n to {0;1}. Boolean functions naturally appear in many areas of mathematics and computer science and constitute a key concept in complexity theory. In this paper we shall study an important problem connected to Boolean functions, a so called Boolean minimization problem, which aims at finding a shortest possible representation of a given Boolean function. The formal statement of the Boolean minimization problem (BM) of course depends on how the input function is represented, and how the size of the output is measured.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů