This HTML5 document contains 43 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n14http://linked.opendata.cz/resource/domain/vavai/projekt/
n6http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n11http://linked.opendata.cz/ontology/domain/vavai/
n15http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F67985840%3A_____%2F10%3A00342826%21RIV11-AV0-67985840/
n18http://linked.opendata.cz/resource/domain/vavai/zamer/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n12http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n17http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n16http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n10http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n13http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n8http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n9http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F67985840%3A_____%2F10%3A00342826%21RIV11-AV0-67985840
rdf:type
skos:Concept n11:Vysledek
dcterms:description
Khrapchenko's classical lower bound n(2) 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) x 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(n(2)) 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. Khrapchenko's classical lower bound n(2) 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) x 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(n(2)) 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.
dcterms:title
On convex complexity measures On convex complexity measures
skos:prefLabel
On convex complexity measures On convex complexity measures
skos:notation
RIV/67985840:_____/10:00342826!RIV11-AV0-67985840
n3:aktivita
n16:P n16:Z
n3:aktivity
P(IAA1019401), Z(AV0Z10190503)
n3:cisloPeriodika
16-18
n3:dodaniDat
n9:2011
n3:domaciTvurceVysledku
n6:8729174
n3:druhVysledku
n13:J
n3:duvernostUdaju
n17:S
n3:entitaPredkladatele
n15:predkladatel
n3:idSjednocenehoVysledku
276680
n3:idVysledku
RIV/67985840:_____/10:00342826
n3:jazykVysledku
n10:eng
n3:klicovaSlova
boolean formula; complexity measure; combinatorial rectangle; convexity
n3:klicoveSlovo
n12:combinatorial%20rectangle n12:complexity%20measure n12:boolean%20formula n12:convexity
n3:kodStatuVydavatele
NL - Nizozemsko
n3:kontrolniKodProRIV
[FA3B9856F03A]
n3:nazevZdroje
Theoretical Computer Science
n3:obor
n8:BA
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
4
n3:projekt
n14:IAA1019401
n3:rokUplatneniVysledku
n9:2010
n3:svazekPeriodika
411
n3:tvurceVysledku
Jukna, S. Kulikov, A. Pudlák, Pavel Hrubeš, P.
n3:wos
000276167000016
n3:zamer
n18:AV0Z10190503
s:issn
0304-3975
s:numberOfPages
13