• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Sharpening complexity results in quantified probability logic
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
October 1, 2026
HSE Researchers Show How Congenital Motor Disorders Affect Brain Development
Researchers from HSE University’s Institute for Cognitive Neuroscience have synthesised the findings of their previous studies on brain development in children with obstetric brachial plexus palsy and arthrogryposis. Their analysis shows that impaired motor function in early childhood not only limits children’s motor experience but also affects memory, categorical thinking, and information processing. The study has been published in Frontiers in Psychology.
October 1, 2026
Window into the Body: Scientists Develop Neural Network to Detect Risk of 15 Diseases from Retinal Images
Russian universities, with the participation of HSE University, Sber, and Z-union, have developed a neural network that can simultaneously assess the risk of 15 types of pathology from retinal photographs, including not only eye diseases but also cardiovascular conditions. The AI system can help clinicians detect potentially concerning changes at an early stage, identify signs reflecting the condition of retinal blood vessels, and determine whether a patient may need further examination. The paper has been published in Frontiers in Medicine.
September 30, 2026
'We Did Not Limit the Time for Questions'
The International Laboratory for Supercomputer Atomistic Modelling and Multi-Scale Analysis at HSE University held a major conference on molecular dynamics. Participants had the opportunity to attend all the presentations, while speakers were given as much time as they needed to answer questions. The HSE News Service interviewed Grigory Smirnov, Head of the Laboratory, and Genri Norman, Chief Research Fellow, about the conference preparations and the discussions it generated.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Sharpening complexity results in quantified probability logic

Logic Journal of the IGPL. 2025. Vol. 33. No. 3. Article jzae114.
Speranski S. O.

We shall be concerned with two natural expansions of the quantifier-free ‘polynomial’ probability logic of [Fagin et al. 1990]. One of these, denoted by QPL-e, is obtained by adding quantifiers over arbitrary events, and the other, denoted by p-QPL-e, uses quantifiers over propositional formulas — or equivalently, over events expressible by such formulas. The earlier proofs of the complexity lower bound results for QPL-e and p-QPL-e relied heavily on multiplication, and therefore on the polynomiality of the basic parts. We shall obtain the same lower bounds for natural fragments of QPL-e and p-QPL-e in which only linear combinations of a very special form are allowed. Also, it will be studied what happens if we add quantifiers over reals.

Language: English
DOI
Keywords: complexityquantificationprobability logicundecidabilitysecond-order arithmetic
Similar publications
Мыслить в сложностности: философский портрет В.И. Аршинова
Knyazeva H., МЕТОД: Московский ежегодник трудов из обществоведческих дисциплин 2025 Т. 5 № 4 С. 176–182
This article analyzes the creative personality and thinking style of Vladimir Ivanovich Arshinov, as well as his distinctive contribution to the philosophy of science – the concept of complexity as an observer embedded in the complexity of the world. Arshinov conceptualized complexity as a key characteristic of self-organizing systems within the context of post-non-classical science ...
Added: October 1, 2026
Reasoning from hypotheses in *-continuous action lattices
Kuznetsov S., Pshenitsyn T., Speranski S. O., Journal of Symbolic Logic 2025 Article jsl.2025.16
The class of all ∗-continuous Kleene algebras, whose description includes an infinitary condition on the iteration operator, plays an important role in computer science. The complexity of reasoning in such algebras — ranging from the equational theory to the Horn one, with restricted fragments of the latter in between — was analyzed by Kozen (2002). This ...
Added: August 12, 2026
О замыкающих ординалах инфинитарных вероятностных исчислений
Speranski S. O., Математические заметки 2026 Т. 120 № 3 С. 470–483
We show that, in terms of closure ordinals, many infinitary calculi for ‘first-order’ logics of probability (i.e., for languages similar to those in [Abadi & Halpern 1994]) are as hard as possible: the corresponding closure ordinals coincide with the least non-constructive ordinal, denoted by $\omega_1^{\mathrm{CK}}$. ...
Added: August 12, 2026
On the complexity of first-order logics of probability
Speranski S. O., Grefenshtein A., Izvestiya. Mathematics 2026 Vol. 90 No. 4 P. 754–775
The article is concerned with Halpern's first-order logics of probability, which we denote by L_1 and L_2 – the first of these deals with probability distributions on the domain, while the second employs distributions on external sets of possible worlds. The proofs of [Abadi & Halpern 1994] of the complexity lower bound results for L_1 and L_2 ...
Added: August 12, 2026
A Big History Perspective on Complexity in Universal Evolution: Conclusions
David J. L., Leonid Grinin, Korotayev A., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 22 P. 585–608.
This collective monograph explores focus on complexity aspects in Big History against the background of complexity growth in the Universe, on our planet, and in biological, social, and cultural systems. Complexity growth is regarded as the connecting thread of evolutionary development and as a leading trend of Big History. The cosmic development chapters examine symmetries ...
Added: August 10, 2026
Human Evolution in the Complexity Growth Perspective: Toward Periodization of the Big History Biosocial Era
Korotayev A., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 13 P. 359–409.
We have undertaken an attempt to propose a periodization of the Big History Biosocial (Anthropogenesis) Era on the basis of the most recent scientific data. This periodization is complexity-based, that is, the boundaries of the identified epochs are marked with complexity jumps, that is, in our case, such phase transitions that result in significant increases ...
Added: August 10, 2026
Biological and Social Phases of Big History and Complexity Growth
Leonid Grinin, Alexander M., Korotayev A., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 12 P. 283–355.
In the first half of this chapter, Grinin et al. survey general similarities and differences between biological and social macroevolution. They undertake a systematic comparison between biological and social evolution at different levels of analysis and in various aspects, formulating a considerable number of general principles and rules of evolution, and working to develop a ...
Added: August 10, 2026
Complexity in Universal Evolution: A Big History Perspective—An Introduction
David J. L., Leonid Grinin, Korotayev A., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 1 P. 1–25.
Complexity is widely acknowledged as a foundational and pivotal concept in Big History, offering a unifying lens through which to examine the emergence and development of systems—from particles and galaxies to life, civilizations, and beyond. Yet, despite its centrality, major gaps remain in how we define, measure, and interpret complexity across different phases and scales. ...
Added: August 10, 2026
On Undecidability Degree of Theory of Figures in Countable and Uncountable Linear Spaces
Dudakov S., Lobachevskii Journal of Mathematics 2025 Vol. 46 No. 12 P. 6092–6102
We study the additive theory of arbitrary figures in linear spaces, that is, the theory of addition extended to sets of vectors. Our main result is the following: if a linear space is infinite, then the additive theory of figures admits interpreting second-order arithmetic and, therefore, it has such or higher degree of undecidability. For countably infinite spaces, ...
Added: May 1, 2026
Невидимые машины: Рассказы о формальной семантике
Tiskin D., М.: Издательская группа URSS, 2026.
Предлагаемая книга представляет собой введение в формальную семантику — раздел языкознания, в котором посредством построения математически строгих моделей исследуется, как предложения приобретают значение и способность передавать информацию в зависимости от своей структуры и значений составляющих их слов. Классические теоретические идеи Г. Фреге, Д. Льюиса, Д. Каплана и др. излагаются современным языком, а при разработке нотации акцент сделан на том, ...
Added: March 17, 2026
Relative Chaoticity of Natural Languages
Yerbolova A. S., Tomashchuk K., Kogan A. et al., Complexity 2026 Vol. 2026 No. 1 Article 5519690
Tis paper presents a novel approach to analyzing and grouping natural languages based on the degree of their chaoticity. It clusters 52 languages from 18 language families, according to the value of the entropy–complexity pair, to reveal the chaotic properties of semantic trajectories. Te obtained clusters appear to be closely correlated with the family of ...
Added: February 16, 2026
Complexity for probability logic with quantifiers over propositions
Speranski S. O., Journal of Logic and Computation 2013 Vol. 23 No. 5 P. 1035–1055
In the present article, the quantifiers over propositions are first introduced into the language for reasoning about probability, then the complexity issues for validity problems dealing with the corresponding hierarchy of probabilistic sentences are investigated. We prove, among other things, the $\Pi^1_1$-completeness for the general validity and also indicate the least level in the hierarchy ...
Added: December 27, 2025
Some new results in monadic second-order arithmetic
Speranski S. O., Computability 2015 Vol. 4 No. 2 P. 159–174
Added: December 27, 2025
Notes on the computational aspects of Kripke’s theory of truth
Speranski S. O., Studia Logica 2017 Vol. 105 No. 2 P. 407–429
The paper contains a survey on the complexity of various truth hierarchies arising in Kripke’s theory. I present some new arguments, and use them to obtain a number of interesting generalisations of known results. These arguments are both relatively simple, involving only the basic machinery of constructive ordinals, and very general. ...
Added: December 26, 2025
Quantifying over events in probability logic: An introduction
Speranski S. O., Mathematical Structures in Computer Science 2017 Vol. 27 No. 8 P. 1581–1600
In this article we describe a bunch of probability logics with quantifiers over events, and develop primary techniques for proving computational complexity results (in terms of m-degrees) about these logics, mainly over discrete probability spaces. Also the article contains a comparison with some other probability logics and a discussion of interesting analogies with research in the metamathematics ...
Added: December 26, 2025
Negation as a modality in a quantified setting
Speranski S. O., Journal of Logic and Computation 2021 Vol. 31 No. 5 P. 1330–1355
The idea of treating negation as a modality manifests itself in various logical systems, especially in Došen's propositional logic N, whose negation is weaker than that of Johansson's minimal logic. Among the interesting extensions of N are the propositional logics N* and Hype; the former was proposed in [Cabalar et al. 2006], while the latter has ...
Added: December 26, 2025
Infinitary action logic with exponentiation
Kuznetsov S., Speranski S. O., Annals of Pure and Applied Logic 2022 Vol. 173 No. 2 Article 103057
We introduce infinitary action logic with exponentiation — that is, the multiplicative-additive Lambek calculus extended with Kleene star and with a family of subexponential modalities, which allow some of the structural rules (contraction, weakening, permutation). The logic is presented in the form of an infinitary sequent calculus. We prove cut elimination and, in the case ...
Added: December 26, 2025
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit