Attributes | Values |
---|
rdf:type
| |
Description
| - We introduce the notions of pseudo-surjective and iterable functions. These two propertiers measure the hardness of the proof complexity generator but unlike the usual hardness they are preserved under composition and iteration.We link the existence of maps with these two properties to the provalibity of circuit lower bounds.
- We introduce the notions of pseudo-surjective and iterable functions. These two propertiers measure the hardness of the proof complexity generator but unlike the usual hardness they are preserved under composition and iteration.We link the existence of maps with these two properties to the provalibity of circuit lower bounds. (en)
- Zavedeme pojem pseudosurjektivních a iterovatelných funkcí. Tyto dvě vlastnosti měří složitosti generátoru v důkazové složitosti a jsou zachovány skládáním a iterováním.Existenci takových funkcí dáme do souvislosti s dokazatelností spodních odhadů pro obvody. (cs)
|
Title
| - Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Duální slabý princip PHP, pseudosurjektivní funkce a dokazatelnost spodních odhadů pro obvody (cs)
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds (en)
|
skos:prefLabel
| - Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Duální slabý princip PHP, pseudosurjektivní funkce a dokazatelnost spodních odhadů pro obvody (cs)
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds (en)
|
skos:notation
| - RIV/67985840:_____/04:00106825!RIV07-AV0-67985840
|
http://linked.open.../vavai/riv/strany
| |
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| - P(IAA1019901), Z(AV0Z1019905)
|
http://linked.open...iv/cisloPeriodika
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/67985840:_____/04:00106825
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - pseudo-surjective functions; pigeonhole principle (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...odStatuVydavatele
| - US - Spojené státy americké
|
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...i/riv/nazevZdroje
| - Journal of Symbolic Logic
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...v/svazekPeriodika
| |
http://linked.open...iv/tvurceVysledku
| |
http://linked.open...n/vavai/riv/zamer
| |
issn
| |
number of pages
| |