Complexity and Probability of Some Boolean Formulas.

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Complexity and Probability of Some Boolean Formulas.

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Complexity and Probability of Some Boolean Formulas.

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F95%2F0976" target="_blank" >GA201/95/0976: HYPERCOMPLEX: Složitostní aspekty superefektivního počítání</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

1998

Kód důvěrnosti údajů

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

Název periodika

Combinatorics, Probability and Computing

ISSN

0963-5483

e-ISSN

—

Svazek periodika

7

Číslo periodika v rámci svazku

N/A

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

13

Strana od-do

451-463

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—