Matematicheskie Zametki
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Mat. Zametki: Year: Volume: Issue: Page: Find

 Mat. Zametki, 2004, Volume 75, Issue 1, Pages 142–150 (Mi mz6)

Complexity of Sets Obtained as Values of Propositional Formulas

A. V. Chernov

M. V. Lomonosov Moscow State University

Abstract: 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.

DOI: https://doi.org/10.4213/mzm6

Full text: PDF file (206 kB)
References: PDF file   HTML file

English version:
Mathematical Notes, 2004, 75:1, 131–139

Bibliographic databases:

UDC: 510.52

Citation: A. V. Chernov, “Complexity of Sets Obtained as Values of Propositional Formulas”, Mat. Zametki, 75:1 (2004), 142–150; Math. Notes, 75:1 (2004), 131–139

Citation in format AMSBIB
\Bibitem{Che04} \by A.~V.~Chernov \paper Complexity of Sets Obtained as Values of Propositional Formulas \jour Mat. Zametki \yr 2004 \vol 75 \issue 1 \pages 142--150 \mathnet{http://mi.mathnet.ru/mz6} \crossref{https://doi.org/10.4213/mzm6} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2054037} \zmath{https://zbmath.org/?q=an:1114.03004} \elib{https://elibrary.ru/item.asp?id=14466486} \transl \jour Math. Notes \yr 2004 \vol 75 \issue 1 \pages 131--139 \crossref{https://doi.org/10.1023/B:MATN.0000015028.10892.68} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000220006100013} 

• http://mi.mathnet.ru/eng/mz6
• https://doi.org/10.4213/mzm6
• http://mi.mathnet.ru/eng/mz/v75/i1/p142

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. A. V. Chernov, “Finite problems and the logic of the weak law of excluded middle”, Math. Notes, 77:2 (2005), 263–272
•  Number of views: This page: 199 Full text: 126 References: 17 First page: 1