Geodesic
Complexity of Sets Obtained as Values of Propositional Formulas
Matematičeskie zametki, Tome 75 (2004) no. 1, pp. 142-150 
A. V. Chernov. Complexity of Sets Obtained as Values of Propositional Formulas. Matematičeskie zametki, Tome 75 (2004) no. 1, pp. 142-150. http://geodesic.mathdoc.fr/item/MZM_2004_75_1_a12/
@article{MZM_2004_75_1_a12,
     author = {A. V. Chernov},
     title = {Complexity of {Sets} {Obtained} as {Values} of {Propositional} {Formulas}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {142--150},
     year = {2004},
     volume = {75},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2004_75_1_a12/}
}
TY  - JOUR
AU  - A. V. Chernov
TI  - Complexity of Sets Obtained as Values of Propositional Formulas
JO  - Matematičeskie zametki
PY  - 2004
SP  - 142
EP  - 150
VL  - 75
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MZM_2004_75_1_a12/
LA  - ru
ID  - MZM_2004_75_1_a12
ER  - 
%0 Journal Article
%A A. V. Chernov
%T Complexity of Sets Obtained as Values of Propositional Formulas
%J Matematičeskie zametki
%D 2004
%P 142-150
%V 75
%N 1
%U http://geodesic.mathdoc.fr/item/MZM_2004_75_1_a12/
%G ru
%F MZM_2004_75_1_a12

Voir la notice de l'article provenant de la source Math-Net.Ru

Interpretation of logical connectives as operations on sets of binary strings is considered; the complexity of a set is defined as the minimum of Kolmogorov complexities of its elements. It is readily seen that the complexity of a set obtained by the application of logical operations does not exceed the complexity of the conjunction of their arguments (up to an additive constant). In this paper, it is shown that the complexity of a set obtained by a formula $\Phi$ is small (bounded by a constant) if $\Phi$ is deducible in the logic of weak excluded middle, and attains the specified upper bound otherwise.

[1] Kolmogoroff A., “Zur Deutung der intuitionistishen Logik”, Mathematische Zeitschrift, 35:1 (1932), 58–65 | DOI | MR | Zbl

[2] Vereschagin N. K., Skvortsov D. P., Skvortsova E. Z., Chernov A. V., “Varianty ponyatiya realizuemosti dlya propozitsionalnykh formul, privodyaschie k logike slabogo zakona isklyuchennogo tretego”, Matem. logika i algebra, Trudy MIAN im. V. A. Steklova, 242, Nauka, M., 2003, 77–97 | MR | Zbl

[3] Plisko V. E., “O yazykakh s konstruktivnymi logicheskimi svyazkami”, Dokl. AN SSSR, 296:1 (1987), 35–38 | MR

[4] Plisko V. E., “Absolyutnaya realizuemost predikatnykh formul”, Izv. AN SSSR. Ser. matem., 47:2 (1983), 315–334 | MR

[5] Shen A., Vereshchagin N., “Logical operations and Kolmogorov complexity”, Theoretical Computer Science, 271 (2002), 125–129 | DOI | MR | Zbl

[6] Yankov V. A., “Ob ischislenii slabogo zakona isklyuchennogo tretego”, Izv. AN SSSR. Ser. matem., 32:5 (1968), 1044–1051 | MR

[7] Medvedev Yu. T., “Finitnye zadachi”, Dokl. AN SSSR, 142:5 (1962), 1015–1018 | MR | Zbl