𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a complexity of the formula (A ⋁ B) ⇒ C

✍ Scribed by K.Yu. Gorbunov

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
285 KB
Volume
207
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

By the complexity KF'(@) of the formula @: (A V B) * C we mean the minimal length of a program which on input (0,A) outputs C and on input (I,@ outputs C. We prove that there exist words A, B, C such that IQ'(@) is close to K(Cl.4) + K( ClB). @ 1998-Elsevier Science B.V. Ail rights reserved K~JNVIYLK Algorithmic information theory; Complexity of formulae; Game approach According to ideas of A.N. Kolmogorov, the problem of estimation of a complexity of a formula of propositional calculus become sensible if we consider each variable as a task of indication of some word, Then each formula also corresponds to a task. For example, the formula A =+-B corresponds to the following task: "given word A construct word B". It is natural to define complexity of this formula as minimal length of a program which on input A outputs B. Clearly, it is conditional Kolmogorob complexity K(BIA).

📜 SIMILAR VOLUMES

A Pieri-Type Formula for H*T(SLn(C)/B)
A Pieri-Type Formula for H*T(SLn(C)/B)
✍ Shawn Robinson 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 173 KB

The singular cohomology of the Grassmann variety of k-planes in n has a basis s ν indexed by partitions. The classical Pieri formula is an explicit rule for determining the coefficients in the expansion of the cup product µ where 1 m is a column of length m and s 1 m is the mth Chern class of the t

On a generalization of the Selberg formu
On a generalization of the Selberg formula
✍ Emmanuel Knafo 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 220 KB

In this paper, we prove a theorem related to the asymptotic formula for ψ k (x; q, a) which is used to count numbers up to x with at most k distinct prime factors (or k-almost primes) in a given arithmetic progression a (mod q). This theorem not only gives the asymptotic formula for ψ k (x; q, a) (o

On a formula of Solomon
On a formula of Solomon
✍ T.A. Springer 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 139 KB