Finite problems and the logic of the weak law of excluded middle

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.Translated from Matematicheskie Zametki, vol. 77, no. 2, 2005, pp. 291–302.Original Russian Text Copyright © 2005 by A. V. Chernov.This revised version was published online in April 2005 with a corrected issue number.