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/