Geodesic
Finite problems and the logic of the weak law of excluded middle
Matematičeskie zametki, Tome 77 (2005) no. 2, pp. 291-302.

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

A new characteristic of propositional formulas as operations on finite problems, the cardinality of a sufficient solution set, is defined. It is proved that if a formula is deducible in the logic of the weak law of excluded middle, then the cardinality of a sufficient solution set is bounded by a constant depending only on the number of variables; otherwise, the accessible cardinality of a sufficient solution set is close to (greater than the nth root of) its trivial upper bound. This statement is an analog of the authors result about the algorithmic complexity of sets obtained as values of propositional formulas, which was published previously. Also, we introduce the notion of Kolmogorov complexity of finite problems and obtain similar results. 
@article{MZM_2005_77_2_a9,
     author = {A. V. Chernov},
     title = {Finite problems and the logic of the weak law of excluded middle},
     journal = {Matemati\v{c}eskie zametki},
     pages = {291--302},
     publisher = {mathdoc},
     volume = {77},
     number = {2},
     year = {2005},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2005_77_2_a9/}
}
TY  - JOUR
AU  - A. V. Chernov
TI  - Finite problems and the logic of the weak law of excluded middle
JO  - Matematičeskie zametki
PY  - 2005
SP  - 291
EP  - 302
VL  - 77
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2005_77_2_a9/
LA  - ru
ID  - MZM_2005_77_2_a9
ER  - 
%0 Journal Article
%A A. V. Chernov
%T Finite problems and the logic of the weak law of excluded middle
%J Matematičeskie zametki
%D 2005
%P 291-302
%V 77
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2005_77_2_a9/
%G ru
%F MZM_2005_77_2_a9
A. V. Chernov. Finite problems and the logic of the weak law of excluded middle. Matematičeskie zametki, Tome 77 (2005) no. 2, pp. 291-302. http://geodesic.mathdoc.fr/item/MZM_2005_77_2_a9/

[1] Kolmogoroff A., “Zur Deutung der intuitionistishen Logik”, Math. Z., 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”, Matematicheskaya logika i algebra, Tr. MIAN, 242, Nauka, M., 2003, 77–97

[3] Chernov A. V., “Slozhnost mnozhestv, poluchennykh kak znacheniya propozitsionalnykh formul”, Matem. zametki, 75:1 (2004), 142–150 | Zbl

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

[5] Medvedev Yu. T., “Ob interpretatsii logicheskikh formul posredstvom finitnykh zadach”, Dokl. AN SSSR, 169:1 (1966), 20–24

[6] Plisko V. E., “O realizuemykh predikatnykh formulakh”, Dokl. AN SSSR, 212:3 (1973), 553–556 | Zbl

[7] Maksimova L. L., Skvortsov D. P., Shekhtman V. B., “Nevozmozhnost konechnoi aksiomatizatsii logiki konechnykh zadach Medvedeva”, Dokl. AN SSSR, 245:5 (1979), 1051–1054 | Zbl

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

[9] Shen A., Vereshchagin N., “Logical operations and Kolmogorov complexity”, Theoret. Computer Sci., 271 (2002), 125–129 | DOI | Zbl

[10] Kolmogorov A. N., “Tri podkhoda k opredeleniyu ponyatiya “kolichestvo informatsii””, Problemy peredachi informatsii, 1:1 (1965), 3–11 | Zbl

[11] Chernov A. V., Finitnye zadachi i logika slabogo zakona isklyuchennogo tretego, Dep. v VINITI 03.07.2003, No. 1263-V2003, MGU, M., 2003