Standard

On convex complexity measures. / Hrubeš, P.; Jukna, S.; Kulikov, A.; Pudlák, P.

в: Theoretical Computer Science, Том 411, № 16-18, 28.03.2010, стр. 1842-1854.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Hrubeš, P, Jukna, S, Kulikov, A & Pudlák, P 2010, 'On convex complexity measures', Theoretical Computer Science, Том. 411, № 16-18, стр. 1842-1854. https://doi.org/10.1016/j.tcs.2010.02.004

APA

Hrubeš, P., Jukna, S., Kulikov, A., & Pudlák, P. (2010). On convex complexity measures. Theoretical Computer Science, 411(16-18), 1842-1854. https://doi.org/10.1016/j.tcs.2010.02.004

Vancouver

Hrubeš P, Jukna S, Kulikov A, Pudlák P. On convex complexity measures. Theoretical Computer Science. 2010 Март 28;411(16-18):1842-1854. https://doi.org/10.1016/j.tcs.2010.02.004

Author

Hrubeš, P. ; Jukna, S. ; Kulikov, A. ; Pudlák, P. / On convex complexity measures. в: Theoretical Computer Science. 2010 ; Том 411, № 16-18. стр. 1842-1854.

BibTeX

@article{4d27d2b02d77407595c18b7c69747b8a,
title = "On convex complexity measures",
abstract = "Khrapchenko's classical lower bound n2 on the formula size of the parity function f can be interpreted as designing a suitable measure of sub-rectangles of the combinatorial rectangle f- 1 (0) × f- 1 (1). Trying to generalize this approach we arrived at the concept of convex measures. We prove the negative result that convex measures are bounded by O (n2) and show that several measures considered for proving lower bounds on the formula size are convex. We also prove quadratic upper bounds on a class of measures that are not necessarily convex.",
keywords = "Boolean formula, Combinatorial rectangle, Complexity measure, Convexity, Matrix norm, Rank",
author = "P. Hrube{\v s} and S. Jukna and A. Kulikov and P. Pudl{\'a}k",
year = "2010",
month = mar,
day = "28",
doi = "10.1016/j.tcs.2010.02.004",
language = "English",
volume = "411",
pages = "1842--1854",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "16-18",

}

RIS

TY - JOUR

T1 - On convex complexity measures

AU - Hrubeš, P.

AU - Jukna, S.

AU - Kulikov, A.

AU - Pudlák, P.

PY - 2010/3/28

Y1 - 2010/3/28

N2 - Khrapchenko's classical lower bound n2 on the formula size of the parity function f can be interpreted as designing a suitable measure of sub-rectangles of the combinatorial rectangle f- 1 (0) × f- 1 (1). Trying to generalize this approach we arrived at the concept of convex measures. We prove the negative result that convex measures are bounded by O (n2) and show that several measures considered for proving lower bounds on the formula size are convex. We also prove quadratic upper bounds on a class of measures that are not necessarily convex.

AB - Khrapchenko's classical lower bound n2 on the formula size of the parity function f can be interpreted as designing a suitable measure of sub-rectangles of the combinatorial rectangle f- 1 (0) × f- 1 (1). Trying to generalize this approach we arrived at the concept of convex measures. We prove the negative result that convex measures are bounded by O (n2) and show that several measures considered for proving lower bounds on the formula size are convex. We also prove quadratic upper bounds on a class of measures that are not necessarily convex.

KW - Boolean formula

KW - Combinatorial rectangle

KW - Complexity measure

KW - Convexity

KW - Matrix norm

KW - Rank

UR - http://www.scopus.com/inward/record.url?scp=77949275187&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2010.02.004

DO - 10.1016/j.tcs.2010.02.004

M3 - Article

AN - SCOPUS:77949275187

VL - 411

SP - 1842

EP - 1854

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 16-18

ER -

ID: 49825643