About: On convex complexity measures

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On convex complexity measures Goto Sponge Distinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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. (en)
Title	On convex complexity measures On convex complexity measures (en)
skos:prefLabel	On convex complexity measures On convex complexity measures (en)
skos:notation	RIV/67985840:_____/10:00342826!RIV11-AV0-67985840
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(IAA1019401), Z(AV0Z10190503)
http://linked.open...iv/cisloPeriodika	16-18
http://linked.open...vai/riv/dodaniDat	2011
http://linked.open...aciTvurceVysledku	Pudlák, Pavel
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Matematický ústav AV ČR, v. v. i.
http://linked.open...dnocenehoVysledku	276680
http://linked.open...ai/riv/idVysledku	RIV/67985840:_____/10:00342826
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	boolean formula; complexity measure; combinatorial rectangle; convexity (en)
http://linked.open.../riv/klicoveSlovo	complexity measure convexity boolean formula combinatorial rectangle
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[FA3B9856F03A]
http://linked.open...i/riv/nazevZdroje	Theoretical Computer Science
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Theories, proofs and computational complexity
http://linked.open...UplatneniVysledku	2010
http://linked.open...v/svazekPeriodika	411
http://linked.open...iv/tvurceVysledku	Pudlák, Pavel Hrubeš, P. Jukna, S. Kulikov, A.
http://linked.open...ain/vavai/riv/wos	000276167000016
http://linked.open...n/vavai/riv/zamer	Rozvoj a prohloubení obecných matematických poznatků a jejich užití v dalších vědních oborech a v praxi
issn	0304-3975
number of pages	13 (xsd:int)

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 84 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software