Logical characterization of complexity class of problems solvable by probablistic algorithms in polynomial time

Abstract

A problem to describe the complexity class BPP in terms of a logical language is considered. BPP (abbreviation for bounded-error probablistic polynomial time) represents the class of computational decision problems that are efficiently solvable in polynomial time. The class BPP has an important practical significance since as it includes the largest spectrum of applied problems. At the same time till now, it was supposed that BPP cannot be characterized because of semantic constraints imposed on Turing machines recognizing languages in BPP. Using a new method of characteristical sets we are the first to provide a logical characterization of the class BPP as a decidable fragment of the second-order logic.

Keywords

• model theory
• computational complexity
• descriptive complexity
• logical characterization
• method of characteristic sets