Complexity and Probability of Some Boolean Formulas.
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F98%3A06010070" target="_blank" >RIV/67985807:_____/98:06010070 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Complexity and Probability of Some Boolean Formulas.
Original language description
The paper describes a construction of a probabilistic distribution on Boolean formulas in a complete basis, such that for every Boolean function f, the probability that the random formula computes f is quasipolynomialy related to exp(-L(f)), where L(f) is the formula size complexity of f. The description of the distribution is based only on syntactic properties of the formulas and allows an efficient generation of the random formulas.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F95%2F0976" target="_blank" >GA201/95/0976: HYPERCOMPLEX:Complexity Issues in High Performance Computing</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
1998
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Combinatorics, Probability and Computing
ISSN
0963-5483
e-ISSN
—
Volume of the periodical
7
Issue of the periodical within the volume
N/A
Country of publishing house
GB - UNITED KINGDOM
Number of pages
13
Pages from-to
451-463
UT code for WoS article
—
EID of the result in the Scopus database
—