On Important Applications of Special Set Decomposition

Stepan Margaryan

doi:doi:10.11648/j.ajmcm.20261101.14

Research Article |

| Peer-Reviewed

On Important Applications of Special Set Decomposition

Stepan Margaryan^*

Published in American Journal of Mathematical and Computer Modelling (Volume 11, Issue 1)

Received: 13 January 2026 Accepted: 26 January 2026 Published: 6 February 2026

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

This paper is devoted to the study of complexity of finding a special covering for a set, as well as to obtaining some important applications of special decomposition. We formulate the problem of existence of a special covering as a decision problem. To determine the complexity class in which this problem is located, we study the relationship between this problem and the Boolean satisfiability problem, treating them as formal languages. We prove that these problems are polynomially equivalent, which means that the problem of existence of a special covering for a set is an -complete problem. In this article we also introduce a new concept ‘Replaceable Subsets’. The properties of such subsets are used to fill in the missing elements needed to obtain a special set covering. It is proved that when searching for missing elements to fill a special covering, the order in which these elements are considered does not matter. This result is of great importance in the search for satisfiability of Boolean functions.

Published in	American Journal of Mathematical and Computer Modelling (Volume 11, Issue 1)
DOI	10.11648/j.ajmcm.20261101.14
Page(s)	39-54
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2026. Published by Science Publishing Group

Keywords

Special Decomposition, Boolean Satisfiability, Equivalence of Problems

1. Introduction

[13]

the concept of a special decomposition of a set and the concept of special covering for a set under such a decomposition are introduced. These concepts have proven to be flexible and easy to use. They can be used in the field of Boolean functions to study important problems, including the satisfiability problem.

In a general sense, the relationship between the complexity classes of various decision problems

[2, 4, 11, 12]

still remains open. However, with the formation of the concept of NP -complete problem, many fundamental studies with significant results appear from time to time. In particular, various complexity classes based on time and space complexity, as well as the relations between them, are widely studied in

[2, 3, 6, 15, 22]

A well-known theoretical study is Schaefer’s result

[20]

, where specific classes of Boolean formulas with certain restrictions are considered. If the formula belongs to one of these classes, then it is decidable in polynomial time. In fact, Schaefer’s dichotomy theorem shows that, depending on the restrictions in a propositional formula, the problem either belongs to the class P or is NP-complete

[2, 4]

. Also, if P ≠ NP, then the formula is in P, if it satisfies certain conditions. In fact, Schaefer considers only the complexity classes P and NP.

Later, Schaefer’s result was refined and extended

[1]

. It is shown that there is also another classification when considering another approach, since there are different problems in P with completely different complexity, which leads to the existence of different complexity classes. As for Schaefer’s classification, unfortunately, some problems arise in determining whether a formula belongs to a given class. It is not always “easy” to check whether a given formula belongs to a given class. A recognition criteria related to this problem is formulated in

[8]

. In addition, the issues of approximation of a function to Schaefer’s classes by fixing some variables of the function are investigated in

[17]

. Also, an estimate of the complexity of such an algorithm is obtained.

An important result was also obtained in

[7]

: it turns out that a number of NP-complete problems remain NP-complete even with a significant restriction on their scope.

We assume that if there exist conditions that completely determine the complexity class of a problem, then the justification of these conditions as applied to a specific problem will most likely be of an algorithmic nature.

In this article we investigate the complexity of finding a special covering for a set. By formulating this problem and the Boolean satisfiability problem as formal languages

[2]

, we prove that these problems are polynomially reducible

[4, 11, 12]

to each other. This means that using the special decompositions, we obtain results for Boolean functions.

One of the important contributions of this article is connected with exploring some of the challenges that arise when searching for a special covering for a set, or equivalently, when searching for satisfiability of a Boolean function.

These results we obtain by introducing new concept of ‘Replaceable Subsets’.

The essence of this concept is by means of permutation of components of some ordered pairs of the special decomposition, collect all elements in some of the domains of the decomposition. For each element, the corresponding ordered pairs are considered separately.

We prove that when searching for missing elements to fill a special covering for the set, the order in which these elements are considered does not matter.

In addition, another result was obtained concerning Boolean functions. It is proven that any I-transformation of a special decomposition of the set of clauses of a function partitions this set into two satisfiable subsets. These results are of great importance in the search for satisfiability of Boolean functions represented in conjunctive normal form.

Another result that may have significant implications for Boolean functions as well. We prove that any Boolean function represented in conjunctive normal form is satisfiable if and only if it can be transformed, according to certain rules, into a function in which every clause contains a negative literal or every clause contains positive literal. These clauses have some similarity with Horn clauses

[5, 9]

, but they are not always the same.

Note also, that the terminology used in relation to the well-known concepts of set theory corresponds to the terminology in

[10, 16, 19, 21]

2. Basic Concepts

Let's recall some definitions, terms and notations from

[13]

, that we will rely on. The sets we will consider are assumed to be ordered unless otherwise stated.

Let the nonempty set S

=

{

e_{1}

e_{2}

,...,

e_{m}

} be given. Let also for some natural number

n

(

M_{1}^{0}

M_{1}^{1}

), (

M_{2}^{0}

M_{2}^{1}

),..., (

M_{n}^{0}

M_{n}^{1}

)

n

arbitrary ordered pairs of arbitrary subsets of the set

S

We use the notation

d_{n} S

for an arbitrarily ordered set of these ordered pairs:

d_{n}

S= {(

M_{1}^{0}

M_{1}^{1}

), (

M_{2}^{0}

M_{2}^{1}

),..., (

M_{n}^{0}

M_{n}^{1}

)}.

The Boolean values

α_{i}

and

{\overset{̅}{α}}_{i}

, for

i

∈ [1,

n

], are used to denote superscripts of subsets:

{\overset{̅}{α}}_{i}

= 0 if

α_{i}

= 1, and

{\overset{̅}{α}}_{i}

= 1 if

α_{i}

= 0.

The tuple of superscripts (

α_{1}

,...,

α_{n}

) of subsets is also called a Boolean tuple.

Definition 2.1. The set

d_{n} S

will be called a special decomposition of the set S, if

1) ∀

i \in

[1,

n

]

{(M}_{i}^{0} \cap M_{i}^{1}

)= ∅,

2) ∀

i \in

[1,

n

] (

M_{i}^{0} \cup M_{i}^{1} \neq

∅),

⋃_{i = 1}^{n} (M_{i}^{0} \cup M_{i}^{1})

= S.

Definition 2.2. Let the set

d_{n}

S be a special decomposition of the set S.

For any Boolean tuple (

α_{1}

α_{2}

,...,

α_{n}

) the ordered set

c_{n}

S ={

M_{1}^{α_{1}}

M_{2}^{α_{2}}

,...,

M_{n}^{α_{n}}

}

will be called a special covering for the set

S

under the special decomposition

d_{n}

S, if

⋃_{i = 1}^{n} M_{i}^{α_{i}}

= S.

Note that for any

i \in

[1,

n

] the subsets

M_{i}^{0}

and

M_{i}^{1}

cannot simultaneously belong to the special covering, but one of them exactly belongs.

Let for some natural number

n

d_{n}

S = {(

M_{1}^{0}

M_{1}^{1}

),..., (

M_{n}^{0}

M_{n}^{1}

)}

be an ordered set of arbitrary ordered pairs of subsets of the set S.

The permutation of the components of some ordered pairs of the set

d_{n} S

, let them be

{

{(M}_{i_{1}}^{0}

M_{i_{1}}^{1})

,...,

(M_{i_{к}}^{0}

M_{i_{к}}^{1}

)}⊆

d_{n} S

if the order of pairs in

d_{n} S

does not change, will be called an I-transformation of the set

d_{n}

S. The resulting set is denoted as

(i_{1}

,...,

i_{k}) I

(

d_{n} S

) or simply as I(

d_{n}

S):

d_{n}

S) =

{(M_{1}^{α_{1}}

M_{1}^{{\overset{̅}{α}}_{1}})

,..., (

M_{n}^{α_{n}}

M_{n}^{{\overset{̅}{α}}_{n}}

)}.

The ordered pairs included in this decomposition are defined as follows:

(

M_{i}^{α_{i}}

M_{i}^{{\overset{̅}{α}}_{i}}

) = (

M_{i}^{0}

M_{i}^{1}

), if the components of the i-th pair are not displaced,

(

M_{i}^{α_{i}}

M_{i}^{{\overset{̅}{α}}_{i}}

) = (

M_{i}^{1}

M_{i}^{0}

), if the components of the i-th pair are displaced.

Obviously, the transition from the set I(

d_{n}

S) to the set

d_{n}

S is also an I-transformation.

Recall that, according to Lemma 1.3 in

[13]

, for any special decomposition of the set S, any

I

-transformation preserve the possibility of being a special decomposition of the set

S

and having a special covering for

S

under such a decomposition.

Thus, with the same pairs of subsets and for any Boolean tuple (

α_{1}

α_{2}

,...,

α_{n}

) in generally the special decomposition looks like

d_{n}

{(M_{1}^{α_{1}}

M_{1}^{{\overset{̅}{α}}_{1}})

,..., (

M_{n}^{α_{n}}

M_{n}^{{\overset{̅}{α}}_{n}}

)}.

We will also use some terms introduced in

[13]

to distinguish the subsets included in ordered pairs of a special decomposition according to the order of their location in these pairs.

The subsets

M_{1}^{α_{1}}

,...,

M_{n}^{α}

are called the subsets of 0-domain,

The subsets

M_{1}^{{\overset{̅}{α}}_{1}}

,...,

M_{n}^{{\overset{̅}{α}}_{n}}

are called the subsets of 1-domain.

If the ordered pair (

M_{n}^{α_{i}}

M_{n}^{{\overset{̅}{α}}_{i}}

)

\in d_{n}

S, then the subset

M_{n}^{α_{i}}

belongs to the

0

-domain and the subset

M_{n}^{{\overset{̅}{α}}_{i}}

belongs to the 1-domain. If the components of this ordered pair are permuted, then the subset

M_{n}^{{\overset{̅}{α}}_{i}}

becomes a subset of the

0

-domain, and the subset

M_{n}^{α_{i}}

becomes a subset of the

1

-domain.

In addition, for any

α \in

{0, 1}, we will use the following notations:

M^{α}

⋃_{i = 1}^{n} M_{i}^{α_{i}}

and

M^{\overset{̅}{α}}

⋃_{i = 1}^{n} M_{i}^{{\overset{̅}{α}}_{i}}

s M^{α}

= {

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}

} and

s M^{\overset{̅}{α}}

= {

M_{1}^{{\overset{̅}{α}}_{1}}

,...,

M_{n}^{{\overset{̅}{α}}_{n}}

The set

s M^{α}

will be called a set of

α

-components or

α

-domain of the decomposition

d_{n} S

(

i_{1}

,...,

i_{k}

M^{α}

is the set obtained by replacing the subsets

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}

with the subsets

M_{1}^{{\overset{̅}{α}}_{1}}

,...,

M_{n}^{{\overset{̅}{α}}_{n}}

, respectively, in the set

s M^{α}

(

i_{1}

,...,

i_{k}

)

s M^{α}

will be called a set of

α

-components of the ordered pairs of decomposition (

i_{1}

,...,

i_{k}

)I(

d_{n}

S).

One of the main goals of the concept special decomposition is to search for a special covering for a given set under a given special decomposition.

With the introduction of the concept of a special decomposition of a set, a problem naturally arises. We will call it a problem of existence of a special covering for a set. Let’s formulate it.

Given a special decomposition of a set. If there exists a special covering for this set under the given special decomposition?

Next, we will study the relationship between this problem and the Boolean Satisfiability Problem.

3. Special Decompositions and Boolean Functions as Formal Languages

Let

f

(

x_{1}

,...,

x_{n}

) be a Boolean function represented in conjunctive normal form (CNF)

[5, 19]

with

m

clauses. It is assumed that the clauses of the function are numbered 1,...,

m

, so we will use the notation

c_{j}

for the

j

-th clause of the function,

j

∈ [1,

m

]. That is,

f

(

x_{1}

,...,

x_{n}

) =

⋀_{j = 1}^{m} c_{j}

The clause

c_{j}

of the literals

x_{i_{1}}^{α_{1}}

,...,

x_{i_{k}}^{α_{k}}

is considered with the following conditions:

c_{j}

x_{i_{1}}^{α_{1}} \lor

...

\lor x_{i_{k}}^{α_{k}}

, where

i_{1}

,...,

i_{k}

k

∈[1,

n

α_{k}

∈{0,1}.

In addition, for any i ∈ [1,

n

x_{i}^{0}

{\overset{̅}{x}}_{i}

and

x_{i}^{1}

x_{i}

For simplicity, we assume that no variable and its negation are included in the same clause simultaneously. Obviously, it does not limit the set of functions being considered.

The Boolean Satisfiability Problem or satCNF problem is the problem of determining whether a given Boolean function

f

(

x_{1}

,...,

x_{n}

) represented in conjunctive normal form is satisfiable, that is, whether there exists a Boolean tuple (

σ_{1}

,...,

σ_{n}

) such that

f

(

σ_{1}

,...,

σ_{n}

) =1.

Our goal is to show that the problem of finding a special covering for a set given a special decomposition of this set is an NP-complete problem

[11]

. To do this, we first form concrete formal languages

[2, 11]

over some alphabets. In general, we will use the following alphabet:

Σ

= {0, 1,

x^{0}

x^{1}

,⋆, ▫,

e

,𝜀}.

However, in some individual cases, for convenience, we use the alphabets

Σ_{1}

= {0, 1,

x^{0}

x^{1}

,⋆}⊆

Σ

and

Σ_{2}

= {0, 1,⋆, ▫,

e

,𝜀}⊆

Σ

The expressions will be represented as strings over these alphabets.

The length of a string is considered to be the number of symbols included in it

[2]

The symbols 0, 1,

x^{0}

x^{1}

will be used to form different literals. The literals will be used with the following meaning:

x_{i}^{0}

x^{0} b

(

i

) =

{\overset{̅}{x}}_{i}

and

x_{i}^{1}

x^{1} b

(

i

) =

x_{i}

We will use also the notation

x_{i}^{α}

meaning that

α \in

{0,1}.

For simplicity we assume that

b

(

i

) is a binary expression of the number

i

. It will be called an index of the literal.

Obviously, the number of variables of the function will also be the number of literals with pairwise different indices included in the clauses of the function.

Similarly, the symbols

e

, 0, 1 will be used to form expressions such as

e_{i}

e b

(

i

), for designation elements of sets, where

b

(

i

) is the binary expression of the number

i

However, when assigning literals and set elements, we will often use subscripts.

The symbols '⋆' and '▫' are separating symbols. And ‘𝜀’ is a special symbol, which will mean the empty string corresponding to the empty set.

Let’s for any natural numbers

n

and

m

define the languages

CLAUSE

(

n

) and CNF(

n

m

) over the alphabet

Σ_{1}

= {0, 1,

x^{0}

x^{1}

,⋆}⊆

Σ

For any Boolean tuple (

α_{1}

,...,

α_{k}

CLAUSE (

n

) = {⟨

x_{i_{1}}^{α_{1}} . . . x_{i_{k}}^{α_{k}}

⟩ / {

x_{i_{1}}^{α_{1}}

,...,

x_{i_{k}}^{α_{k}}

} is a set of literals such that (k,

i_{j}

∈ [1,

n

]) & (

i_{r} \neq i_{l}

, if r

\neq

l)}.

It is important to note, that the language CLAUSE(

n

) does not contain an empty string. Also, it does not contain a string that includes any variable and its negation simultaneously.

We will say that the string

⟨

x_{i_{1}}^{α_{1}} x_{i_{2}}^{α_{2}} . . . x_{i_{k}}^{α_{k}}

⟩ corresponds to the set {

x_{i_{1}}^{α_{1}}

x_{i_{2}}^{α_{2}}

,...,

x_{i_{k}}^{α_{k}}

}

as well as we will say that the string is formed by the clause.

Let

c_{j_{i}}

for different indices denote different strings included in the language CLAUSE(

n

). Then, we define the language CNF(

n

m

) as follows:

CNF(

n

m

) = {⟨

c_{j_{1}}

⋆

c_{j_{2}}

⋆... ⋆

c_{j_{m}}

⟩ / ∀

i

∈ [1,

m

c_{j_{i}} \in

CLAUSE(

n

)}.

Let's now consider the alphabet

Σ_{2}

= {0, 1, ⋆, ▫,

e

, 𝜀}. Using the symbols

e

, 0 and 1, we compose expressions over the

Σ_{2}

to denote elements of an arbitrary set

=

{

e_{j_{1}}

e_{j_{2}}

, ...,

e_{j_{m}}

Since the empty subset plays an important role in the special decomposition, we need a symbol for forming the strings corresponding to the pairs of subsets with an empty component. That is, we will use some symbol to form strings corresponding to the ordered pairs of subsets, such as (M, ∅) or (∅, M) for some nonempty subset M. Let 𝜀 ∈ Σ be such a symbol.

Now for a natural number

m

we define the languages

SAB

(

m

{SAB}^{ε}

(

m

) and

PAIR

(

m

) over the alphabet

Σ_{2}

as follows:

SUB(

m

) = {⟨

e_{j_{1}} e_{j_{2}}

...

e_{j_{k}}

⟩/ (k ∈ [1,

m

]) & (

j_{p} \neq j_{q}

, if

p \neq q

)}.

{SUB}^{ε}

(

m

) = {𝜀}

\cup

SUB(

m

Note that the language

SAB

(

m

) does not contain an empty string.

We say that the string M = ⟨

e_{j_{1}} e_{j_{2}}

...

e_{j_{k}}

⟩ corresponds to the set {M } = {

e_{j_{1}}

e_{j_{2}}

,...,

e_{j_{k}}

} or the string M is formed by the set {M }.

For any set N, we denote by ⟨N ⟩ the string that is formed by the set N. This means that for a set

N

of at most

m

elements ⟨

N

⟩

\in SUB

(

m

With such designation we define the language PAIR(

m

PAIR (

m

) = {⟨M ▫ N⟩ / (M

\in {SUB}^{ε}

(

m

)) & (N

\in {SUB}^{ε}

(

m

)) & ({M} ⋂ {N } = ∅) & (M

\cup

\neq \emptyset

)}

Note that for any strings M

\in {SUB}^{ε}

(

m

) and N

\in {SUB}^{ε}

(

m

), we consider the string ⟨M ▫ N ⟩ to be an ordered pair of strings M and N. Also, for any natural number

m

⟨M ▫ 𝜀⟩

\in

PAIR(

m

) and ⟨𝜀 ▫ N⟩

\in

PAIR(

m

)

only with {M }

\neq

∅ and {N }

\neq

∅.

For convenience, we will use subscripts and superscripts to distinguish between the notation of the substrings included in

PAIR

(

m

). That is, for some natural number

i

, we will use the notation ⟨

M_{i}^{α}

▫

M_{i}^{\overset{̅}{α}}

⟩ for the string ⟨M ▫ N ⟩∈ PAIR(

m

). Then, for any natural numbers

n

and

m

, we define the language

d

(

n

m

) over the alphabet

Σ_{2}

n

m

) =

{

⟨

M_{1}^{α}

▫

M_{1}^{\overset{̅}{α}}

⋆... ⋆

M_{n}^{α}

▫

M_{n}^{\overset{̅}{α}}

⟩ ̸ ∀

i

∈ [1,

n

] ⟨

M_{i}^{α}

▫

M_{i}^{\overset{̅}{α}}

⟩

\in

PAIR(

m

), and

m

is the number of elements with pairwise different indices in all subsets}.

The evidence for the following statements is obvious.

Proposition 3.1. For any natural numbers

n

and

m

, holds the following:

1) if ⟨

x_{i_{1}}^{α_{1}}

...

x_{i_{k}}^{α_{k}}

⟩

\in

CLAUSE(

n

), and the set {

x_{l_{1}}^{β_{1}}

,...,

x_{l_{k}}^{β_{k}}

} is any permutation of the set of literals {

x_{i_{1}}^{α_{1}}

,...,

x_{i_{k}}^{α_{k}}

}, then also ⟨

x_{i_{1}}^{β_{1}}

,...,

x_{i_{k}}^{β_{k}}

⟩

\in

CLAUSE(

n

2) if ⟨

c_{j_{1}}

⋆... ⋆

c_{j_{m}}

⟩

\in

CNF(

n

m

), and the set {

c_{l_{1}}

,...,

c_{l_{m}}

} is any permutation of the set {

c_{j_{1}}

,...,

c_{j_{m}}

}, then ⟨

c_{l_{1}}

⋆... ⋆

c_{l_{m}}

⟩

\in

CNF(

n

m

3) ⟨

c_{j_{1}}

⋆... ⋆

c_{j_{m}}

⟩

\in

CNF(

n

m

) if and only if the clauses corresponding to the strings designated as

c_{j_{1}}

c_{j_{2}}

,...,

c_{j_{m}}

form a certain function

f

, represented in CNF with

n

variables and with

m

clauses.

4) if the string ⟨

e_{j_{1}}

...

e_{j_{k}}

⟩ ∈ SUB(

m

) and the set {

e_{l_{1}}

,...,

e_{l_{k}}

} is any permutation of the set {

e_{j_{1}}

, ...,

e_{j_{k}}

}, then ⟨

e_{l_{1}}

...

e_{l_{k}}

⟩ ∈ SUB(

m

5) if ⟨M ▫ N⟩ ∈ PAIR(

m

) then ⟨N ▫ M ⟩ ∈ PAIR(

m

6) if ⟨

M_{1}^{α}

▫

M_{1}^{\overset{̅}{α}}

⋆... ⋆

M_{n}^{α}

▫

M_{n}^{\overset{̅}{α}}

⟩ ∈ d(

n

m

) and the set

{(M_{i_{1}}^{α}

M_{i_{1}}^{\overset{̅}{α}}

),..., (

M_{i_{n}}^{α}

M_{i_{n}}^{\overset{̅}{α}}

)} is any permutation of the set {(

M_{1}^{α}

M_{1}^{\overset{̅}{α}}

),..., (

M_{n}^{α}

M_{n}^{\overset{̅}{α}}

)} then

⟨

M_{i_{1}}^{α}

▫

M_{i_{1}}^{\overset{̅}{α}}

⋆... ⋆

M_{i_{n}}^{α}

▫

M_{i_{n}}^{\overset{̅}{α}}

⟩ ∈ d(

n

m

)

7) ⟨

M_{1}^{α}

▫

M_{1}^{\overset{̅}{α}}

⋆... ⋆

M_{n}^{α}

▫

M_{n}^{\overset{̅}{α}}

⟩

\in

n

m

) if and only if the set

S

⋃_{i = 1}^{n} (\{M_{i}^{α}\} \cup \{M_{i}^{\overset{̅}{α}}\})

consists of

m

elements and the ordered set of ordered pairs

{({

M_{1}^{α}

}, {

M_{1}^{\overset{̅}{α}}

}),..., ({

M_{n}^{α}

}, {

M_{n}^{\overset{̅}{α}}

})}, is a special decomposition of the set S, where ⟨

M_{i}^{α}

⟩ corresponds to the set {

M_{i}^{α}

} for

i

∈ [1,

n

Thus, strings of different languages have some basic properties of the corresponding sets.

Sometimes, if it does not lead to an ambiguity, we will use the notation M instead of {M} for the set corresponding to the string ⟨M ⟩.

To estimate the complexity of recognizing these languages, we turn to Turing machines using definitions in

[2, 11, 14]

. Note that we need to specify the input data for any language. Actually, we have defined these languages for any natural numbers, and the membership of strings to languages depends on these numbers. So, for any language, we compare the corresponding parameters with these numbers. For any string

w

we will use |

w

| to denote the number of symbols included in it.

Proposition 3.2. For any natural number

n

and

m

, there exist Turing machines

T_{C}

T_{CNF}

T_{SUB}

T_{PAIR}

and

T_{d}

that recognize the languages CLAUSE(

n

), CNF(

n

m

), SUB(

m

), PAIR(

m

), and d(

n

m

), respectively, in polynomial time.

Proof. (i) Let

w

be a string over the alphabet Σ. We assume that Σ is also an alphabet for each simulated Turing machine. It is convenient and easy simulate a 4-tape Turing machines with an input tape, two work tapes and an output tape

[2]

Let’s describe the general workflow of

T_{C}

. Receiving the string

w

T_{C}

does:

(i.1) checks if

w

starts with one of the symbols

x^{0}

x^{1}

(i.2) checks whether a binary code follows any occurrence of the symbol

x^{0}

x^{1}

(i.3) checks if one of the characters

x^{0}

x^{1}

, or the special symbol "end of string", follows the binary code. Meanwhile, if

T_{C}

encounters an "end of string" symbol, it stops.

(i.4) checks whether the index of current literal is less than or equal to

n

(i.5) checks, whether the index of the current literal differs from the indices of other literals included in the string.

If any of the points (i.1) - (i.5) has a negative answer,

T_{C}

rejects the string, otherwise it continues to work until it has considered all pairs.

It is easy to see that with the described workflow, for any natural number

n

T_{C}

accepts only the strings belonging to the language CLAUSE(

n

) and rejects all other strings.

Obviously, the total number of operations required to perform the points (i.1) - (i.3), does not exceed the number

c ⨉

w

| for some constant

c

. Consider the points (i.4) and (i.5):

(i.4) to compare the literal indices with the number

n

T_{C}

records the number

n

on the first work tape, the index of the current literal on the second work tape, and does the following:

1) if the index length is greater than the length of n’s record, then

T_{C}

rejects the string

w

2) if the length of index is less than the length of n’s record, then

T_{C}

records the next literal index on the second work tape and continues working,

3) if the lengths are equal,

T_{C}

runs over both records on work tapes and compares corresponding binary digits with the same orders in these records. If, in the same order, 0 occurs on the first tape, and 1 on the second tape,

T_{C}

rejects the string

w

, otherwise continues working.

Thus,

T_{C}

records each index on the second tape, compares its length with the

n

’s length and compares its digits with n’s digits. So, it needs no more than

c ⨉

w

| operations for some constant

c

(i.5) let the condition (i.1) - (i.4) be satisfied. This means that the string

w

has the form

w

=⟨

x_{i_{1}}^{α_{1}}

...

x_{i_{k}}^{α_{k}}

⟩

and

T_{C}

will check if the binary numbers

i_{1}

,...,

i_{k}

are pairwise distinct. It is easy to notice that

w

| =|

i_{1}

| +... +|

i_{k}

| +

k

For the point (i.5)

T_{C}

considers all pairs of literal indices looking for a pair of literals with the same indices:

i_{j}

i_{l}

. So,

T_{C}

sequentially records the pairs on work tapes, runs over both records and compares corresponding binary digits in the same orders in these records. If a pair of different digits occurs in the current order or the lengths of records are different,

T_{C}

moves on to comparing other pairs of indices, otherwise it rejects the string

w

Obviously,

T_{C}

requires no more than c

⨉

min(|

i_{j}

|, |

i_{l}

|) operations for some constant c, to compare the pair of indices

i_{j}

and

i_{l}

It is also easy to prove that the total number of comparison operations of all pairs of literal indices included in the string

w

does not exceed the number c

⨉ {(| w |)}^{2}

for some constant c.

(ii) Let’s now estimate the complexity of recognizing the language CNF(

n

m

) for any natural numbers

n

and

m

. We describe the general workflow of Turing machine

T_{CNF}

, that accepts the string

w

, if

w

∈ CNF(

n

m

) and rejects it otherwise. Receiving the string

w

T_{CNF}

does:

(ii.1) checks if the number of occurrences of the symbol ‘⋆’ is equal to (

m

– 1),

(ii.2) checks whether any occurrence of the character "⋆" in the string is located between a binary digit and a literal.

(ii.3) checks whether any substring is one of the following positions in the string

w

1) between the start and the symbol "⋆",

2) between two symbols "⋆",

3) between the symbol "⋆" and the symbol ‘end of string’, and does not contain the symbol "⋆", is belongs to the language CLAUSE(

n

If any of the points (ii.1) - (ii.3) has a negative answer,

T_{CNF}

rejects the string, otherwise it accepts the string

w

. It is easy to see that with the described workflow, for any natural number

n

and

m

T_{CNF}

accepts only the strings belonging to the language CNF(

n

m

) and rejects all other strings.

Obviously, the total number of operations required to perform the points (ii.1) and (ii.2), does not exceed the number

c ⨉

w

| for some constant

c

With regard to point (ii.3), if (ii.1) and (ii.2) are satisfied, then

w

looks like

w

=⟨

c_{j_{1}}

⋆

c_{j_{2}}

⋆...⋆

c_{j_{m}}

⟩,

where

c_{j_{1}}

c_{j_{2}}

,...,

c_{j_{m}}

are clauses. According to point (i.5), these clauses are recognized by Turing machines in no more than

⨉

(

{| c_{j_{1}} |}^{2}

{| c_{j_{2}} |}^{2}

+... +

{| c_{j_{m}} |}^{2}

)

operations for some constant c. On the other hand, it is obvious that

(

{| c_{j_{1}} |}^{2}

{| c_{j_{2}} |}^{2}

+... +

{| c_{j_{m}} |}^{2}

)

\leq (| {c_{j_{1}} | + | c_{j_{2}} | + . . . + | c_{j_{m}} |)}^{2}

Therefore, it is easy to see, that the total number of operations required to accept or reject the string

w

, does not exceed the number c

⨉ {(| w |)}^{2}

(iii) The general operating principles of the Turing machine

T_{SAB}

are similar to those of the

T_{C}

. To recognize the string of the language SUB(

m

T_{SUB}

does the following:

(iii.1) checks whether the string

w

starts with the symbols

e

(iii.2) checks whether a binary code follows any occurrence of the symbol

e

(iii.2) checks whether the current binary code is followed by the symbol

e

or the special symbol "end of string".

(iii.4) checks whether the number of occurrences of the symbol

e

is less than or equal to

m

(iii.5) checks, whether the index of the current literal differs from the indices of other literals included in the string.

If any of these points has a negative answer,

T_{SUB}

rejects the string and accepts it otherwise.

Obviously, to accept or reject the string

w

T_{SUB}

needs no more than c

⨉ {(| w |)}^{2}

operations.

(iv) The general operating principles of the Turing machine

T_{PAIR}

To recognize the string

w

of the language PAIR(

m

T_{PAIR}

does the following:

(iv.1) checks whether

w

consists of two substrings separated by the symbol ‘▫’.

(iv.2) checks whether these substrings are included in the language

{SUB}^{ε}

(

m

(iv.3) checks whether the intersection of these substrings is empty.

(iv.4) checks whether one of the substrings differs from

ε

Taking into account the previous reasoning, it can be argued that the total number of operations required to accept or reject a string

w

does not exceed the number c

⨉ {(| w |)}^{2}

(v) Let’s now describe the general workflow of Turing machine

T_{d}

that recognizes the string of language d(

n

m

) in a polynomial time.

That is, receiving the string w, the Turing machine

T_{d}

runs over it and does:

(v.1) checks if the string w consists of

n

substrings separated from each other by (

n

– 1) symbols '⋆'.

(v.2) checks whether each substring is included in PAIR(

m

(v.3) checks whether the number of elements with pairwise different indices in the string

w

is equal to

m

If any of those conditions is not satisfied, then the

T_{d}

rejects the string.

To estimate the number of operations for point (v.1), It is enough to check:

1) whether the number of occurrences of the symbol '⋆' is equal to (

n

– 1),

2) whether any occurrence of the symbol '⋆' is located between some binary code and the symbol

e

Obviously, the number of required operations does not exceed the number c

⨉

|w |.

Point (v.2): let |

w_{i}

| be the number of symbols included in the

i

-th substring. Then, to check if the

i

-th substring is included in PAIR(

m

T_{d}

needs to perform c

⨉ {(| w_{i} |)}^{2}

operations. Since |

w_{1}

| + |

w_{2}

| +... + |

w_{n}

\leq

|w|, then to check if all substrings are included in

PAIR

(

m

T_{d}

needs to perform c

⨉ {(| w |)}^{2}

operations.

Point (v.3): if (v.1) and (v.2) are satisfied, then the string

w

contains elements with binary codes. Receiving the string w,

T_{d}

does the following:

1) records

w

on the first work tape, and marks an element in it. Let it be the element

e_{j}

2) records

e_{j}

on the second work tape.

T_{d}

runs over the string

w

and sequentially compares all non-marked elements in it with the element

e_{j}

. All elements in that have the same index as

e_{j}

are marked.

Running through the entire string w,

T_{d}

continues as follows:

1) records

e_{j}

on the output tape,

2) looks for the next non-marked element in

w

and, finding it, repeats the described operations.

If there are no unmarked elements left in w, then obviously the output tape contains all elements with pairwise distinct indices. So,

T_{d}

compares their number with

m

Taking into account the arguments in (i.5), it can be argued that the number of needed operations does not exceed the number

c ⨉ {| w |}^{2}

Thus, strings of any of the described languages are recognized in polynomial time with respect to the length of the input string.

\nabla

4. Reducibility of Languages

Although there are different definitions of the concept of polynomial reducibility

[4, 11, 18]

, in general they all express a similar relationship between different languages. In this section we will study the reducibility of the Boolean satisfiability problem to the problem of existence of a special covering for a set and vice versa. We will use definitions from

[2, 11]

Let we are given a Boolean function

f

(

x_{1}

,...,

x_{n}

) represented in conjunctive normal form with

m

clauses, and let S = {

e_{1}

e_{2}

,...,

e_{m}

} be any non-empty tuple of

m

elements. Recall that we use the notation

e_{j}

for instead of the string

e b

(

j

) of the alphabet

Σ_{2}

To each element of the set S, we associate a clause of the function

f

(

x_{1}

,...,

x_{n}

) so that the element

e_{j}

= eb(

j

) corresponds to the

j

-th clause of the function in the sequential enumeration of the clauses. We will call eb(j) the number or the code of the clause, and will identify it with its corresponding clause. So, for brevity, we will denote the set of clauses of the function

f

(

x_{1}

,...,

x_{n}

) as S(

f

) = {

e_{1}

,...,

e_{m}

} and use these elements as clauses. So, the entry

x_{i}^{α_{i}} \in e_{j}

will mean the inclusion of the literal

x_{i}^{α_{i}}

in the clause corresponding to

e_{j}

. Also, the notation ⟨

e_{j}

⟩ ∈ CLAUSE(

n

), will mean that the clause corresponding to

e_{j}

belongs to the language CLAUSE(

n

) and the string ⟨

e_{j}

⟩ is formed by the clause

e_{j}

. So, we designate the following string by

f_{n}

f_{n}

=⟨

e_{1}

⋆

e_{2}

⋆...⋆

e_{m}

⟩,

Obviously,

f_{n}

will be the string corresponding to the function

f

(

x_{1}

,...,

x_{n}

) in conjunctive normal form, and

f

(

x_{1}

,...,

x_{n}

) will be a function corresponding to the string

f_{n}

. To denote the subsets of clauses will be used the capital letters corresponding to the function designation:

For some i

\in

[1,

n

] we form the following sets:

F_{i}^{0}

= {

e_{j}

e_{j}

∈ S(

f

) and

{\overset{̅}{x}}_{i} \in e_{j}

} and

F_{i}^{1}

= {

e_{j}

e_{j}

∈ S(

f

) and

x_{i} \in e_{j}

Obviously,

F_{i}^{0}

⊆

S

(

f

) and

F_{i}^{1}

⊆ S(

f

Proposition 4.1. If for some natural numbers

n

and

m

f_{n}

∈ CNF(

n

m

), then

1) ∀ i ∈ [1,

n

] ⟨

F_{i}^{0}

▫

F_{i}^{1}

⟩

\in

PAIR(

m

⋃_{i = 1}^{n} {(F}_{i}^{0} \cup F_{i}^{1})

= S

(f)

Proof. To proof of (i) it is enough to prove that for any

i \in

[1,

n

1) ⟨

F_{i}^{0}

⟩

\in {SUB}^{ε}

(

m

) and ⟨

F_{i}^{1}

⟩

\in {SUB}^{ε}

(

m

F_{i}^{0}

⋂

F_{i}^{1} =

∅,

F_{i}^{0} \cup F_{i}^{1} \neq

∅,

The proof follows from definitions of languages

{SUB}^{ε}

(

m

), PAIR(

m

) and CNF(

n

m

The proof of (ii) follows from the definitions of the sets

f M_{i}^{α}

and

{fM}_{i}^{\overset{̅}{α}}

\nabla

Lemma 4.2. For any natural numbers

n

and

m

and for any string

f_{n} \in

CNF(

n

m

), there exists a Turing machine that, receiving the string

f_{n}

, outputs the string ⟨

F_{1}^{0}

▫

F_{1}^{1}

⋆... ⋆

F_{n}^{0}

▫

F_{n}^{1}

⟩ in polynomial time with respect to the length of the string

f_{n}

Proof. Let’s describe the general workflow of such a Turing machine, with alphabet

Σ

Similar to Proposition 3.2, we will use a Turing machine denoted by

T_{1}

, with input tape, output tape and with two work tapes

[2]

. The

T_{1}

’s operation procedure consists of following stages:

Receiving a string of clauses,

T_{1}

records the codes of clauses on the first work tape in the same order in which the clauses are on the input tape.

To form the current strings

F_{i}^{0}

and

F_{i}^{1}

for

i

∈ [1,

n

T_{1}

uses the second work tape, successively recording the pairs (

i

, 0) and (

i

, 1) on it. We say that

T_{1}

scans a code or a pair of indices, meaning that it scans the symbols that form them.

After recording the numbers of clauses,

T_{1}

starts working, recording (1, 0) on the second work tape and 𝜀 on output tape.

Еach action of

T_{1}

is determined by configuration of four records on different tapes scanned at current moment. We denote it (

H_{1}

H_{2}

H_{3}

H_{4}

) with the following meanings:

H_{1}

is current scanned record on input tape,

H_{2}

is current scanned record on first work tape,

H_{3}

is current scanned record of pair (

i

, 0) on the second work tape, where

i

∈ [1,

n

H_{4}

is current scanned record on output tape.

The first configuration is (

x_{j}^{α}

e_{1}

, (

1

, 0), 𝜀),

x_{j}^{α}

is the first symbol of the string

f_{n}

α \in

{0, 1}.

Аt the beginning of the work,

T_{1}

scans these records on the tapes.

To form

F_{i}^{0}

and

F_{i}^{1}

T_{1}

performs actions depending on configuration:

with configuration (

{\overset{̅}{x}}_{i}

e_{j}

, (

i

, 0), 𝜀),

1) records

e_{j}

instead of 𝜀, on the output tape,

2) scans the symbol

e_{j}

on the output tape,

3) scans the symbol following of

{\overset{̅}{x}}_{i}

on the input tape,

with configuration (

{\overset{̅}{x}}_{i}

e_{j}

, (

i

, 0),

e_{k}

1) adds

e_{j}

to the output tape and scans it,

2) scans the symbol following of

{\overset{̅}{x}}_{i}

on the input tape,

with configuration (

{\overset{̅}{x}}_{i}

e_{j}

, (

s

, 0), 𝜀) or (

{\overset{̅}{x}}_{i}

e_{j}

, (

s

, 0),

e_{k}

), where

i \neq s

scans the symbol following of

{\overset{̅}{x}}_{i}

on the input tape,

with configuration (⋆,

e_{j}

, (

i

, 0),

e_{k}

1) scans the symbol

e_{j + 1}

on the first work tape

2) scans the symbol following of the symbol '⋆' on the input tape,

with configuration (end of input string,

e_{j}

, (

i

, 0),

e_{k}

1) adds the symbol ‘▫’ after

e_{k}

on the output tape,

2) records the pair (

i

, 1) on the next place following the pair (

i

, 0) and scans it,

3) - records the symbol 𝜀 after the symbol ‘▫’ on the output tape and scans it,

4) scans the first symbol on input tape,

with configuration (

{\overset{̅}{x}}_{i}

e_{j}

, (

s

, 1), 𝜀) or (

{\overset{̅}{x}}_{i}

e_{j}

, (

s

, 1),

e_{k}

scans the symbol following of

x_{i}^{α}

on the input tape,

with configuration (end of input data,

e_{j}

, (

i

, 1),

e_{k}

) and for

i

n

1) adds the symbol ‘⋆’ on the next place following the

e_{k}

on output tape,

2) records the symbol 𝜀 on the next place of ‘⋆’ on the output tape and scans it,

3) records the pair (

i

+1, 0) on the next place following the pair (

i

, 1) on the second work tape and scans it,

scans the first symbol on input tape,

with (end of input data,

e_{j}

, (

n

, 1),

e_{k}

), the Turing's machine

T_{1}

stops.

It is easy to see that

T_{1}

outputs the string

⟨

F_{1}^{0}

▫

F_{1}^{1}

⋆...⋆

F_{n}^{0}

▫

F_{n}^{1}

⟩.

Also, the number of actions performed by

T_{1}

to complete the described procedure is polynomial with respect to the length of input data of the string

f_{n}

, denoted by |

f_{n}

|. More precisely, the number of mentioned operations does not exceed the number

c ⨉ {| f_{n} |}^{2}

for certain constant

c

\nabla

Let's denote by

T_{1}

(

f_{n}

) the string formed as a result of

T_{1}

's work on input

f_{n}

T_{1}

(

f_{n}

)=⟨

F_{1}^{0}

▫

F_{1}^{1}

⋆...⋆

F_{n}^{0}

▫

F_{n}^{1}

⟩.

Lemma 4.3. For any natural numbers

n

and

m

f_{n} \in

CNF(

n

m

)if and only if

T_{1}

(

f_{n}

)

\in d

(

n

m

Proof. Obviously, if

f_{n} \in

CNF(

n

m

) then, according to Proposition 4.1 i),

T_{1}

(

f_{n}

) =⟨

F_{1}^{0}

▫

F_{1}^{1}

⋆...⋆

F_{n}^{0}

▫

F_{n}^{1}

⟩

\in

n

m

Now, suppose that

T_{1}

(

f_{n}

)

\in

n

m

). In this case for any

i \in

[1,

n

] the following holds:

F_{i}^{0} ⋂ F_{i}^{1} =

∅, thus, no clause is included in the subsets

F_{i}^{0}

and

F_{i}^{1}

simultaneously.

F_{i}^{0} \cup F_{i}^{1} \neq

∅, that is

F_{i}^{0} \neq

∅ or

F_{i}^{1} \neq

∅.

In fact, for any

i \in

[1,

n

], we get the following:

1) there is no clause including the literals

{\overset{̅}{x}}_{i}

and

x_{i}

simultaneously.

2) the literal

{\overset{̅}{x}}_{i}

is included in some clause or the literal

x_{i}

is included in some clause.

It means that the number of literals with pairwise different indexes is equal to

n

In addition, each clause

e_{j}

included in some set

F_{i}^{α}

cannot be empty, since if

e_{j} \in F_{i}^{α}

, then

x_{i}^{α} \in e_{j}

. Therefore

f_{n} \in

CNF(

n

m

\nabla

We denote by

dS (f)

the special decomposition of the set of clauses of the function

f

(f)

={(

F_{1}^{0}

F_{1}^{1}

),..., (

F_{n}^{0}

F_{n}^{1}

)}.

If there is a special covering for S

(f)

in the decomposition dS(

f

), we denote it as

c_{n}

f

)

[13]

c_{n}

f

)={

F_{1}^{α_{1}}

F_{2}^{α_{2}}

,...,

F_{n}^{α_{n}}

For natural numbers

n

and

m

, we define the languages sat

CNF

(

n

m

) and sC(

n

m

): satCNF(

n

m

) = {⟨

f_{n}

⟩ /

f

is in CNF with

m

clauses and

f

is a satisfiable function}, sC(

n

m

) = {⟨

M_{1}^{0}

▫

M_{1}^{1}

⋆... ⋆

M_{n}^{0}

▫

M_{n}^{1}

⟩

\in

n

m

)/there is a tuple (

α_{1}

,...,

α_{n}

) suchthat

⋃_{i = 1}^{n} {{M}_{i}^{α_{i}}}

⋃_{i = 1}^{n} {({M}_{i}^{0}} \cup {M_{i}^{1}})

Theorem 4.4. For any natural numbers

n

and

m

f_{n} \in

satCNF(

n

m

) if and only if

T_{1}

(

f_{n}

)

\in

sC(

n

m

Proof. Suppose that for some natural

n

and

m

f_{n} \in

sat

CNF

(

n

m

) and

f

(

x_{1}

,...,

x_{n}

) is the function corresponding to the string

f_{n}

. According to the definition,

f

(

x_{1}

,...,

x_{n}

) is represented in conjunctive normal form with

m

clauses and is a satisfiable function. That is, there is a Boolean tuple (

σ_{1}

,...,

σ_{n}

) such, that

f

(

σ_{1}

,...,

σ_{n}

) =1.

We show, that the set {

F_{1}^{σ_{1}}

F_{2}^{σ_{2}}

,...,

F_{n}^{σ_{n}}

} is a special covering for the set

S (f)

By Proposition 4.1 and Lemma 4.3, it suffices to prove that

⋃_{i = 1}^{n} F_{i}^{σ_{i}}

S (f)

. Let's show that any clause of the set

S (f)

is included in some subset

F_{i}^{σ_{i}}

⊆{

F_{1}^{σ_{1}}

F_{2}^{σ_{2}}

,...,

F_{n}^{σ_{n}}

}

Let there be a clause

e_{j}

that is not included in any of these subsets. This means that none of the literals

x_{1}^{σ_{1}}

,...,

x_{n}^{σ_{n}}

is included in the clause

e_{j}

, and thus

e_{j}

is a disjunction of some literals of the form

x_{i}^{{1 - σ}_{i}}

. Since

σ_{i}^{{1 - σ}_{i}} =

0 for any i ∈ [1,

n

], then for given assignment of variables

e_{j}

= 0, which contradicts the assumption that

f

(

σ_{1}

,...,

σ_{n}

) =1. Therefore, any clause is included in some subset

F_{i}^{σ_{i}}

that is included in the set {

F_{1}^{σ_{1}}

F_{2}^{σ_{2}}

,...,

F_{n}^{σ_{n}}

}, So this set is a special covering for S(

f

⋃_{i = 1}^{n} F_{i}^{σ_{i}}

⋃_{i = 1}^{n} {({F}_{i}^{0}} \cup {F_{i}^{1}})

Therefore,

T_{1}

(

f_{n}

) =⟨

F_{1}^{α}

▫

F_{1}^{\overset{̅}{α}}

⋆...⋆

F_{n}^{α}

▫

F_{n}^{\overset{̅}{α}}

⟩

\in sC

(

n

m

Now assume that for some natural numbers

n

and

m

T_{1}

(

f_{n}

)

\in

sC(

n

m

). This means that

T_{1}

(

f_{n}

)

\in d

(

n

m

) and there are (

σ_{1}

,...,

σ_{n}

) such that the set {

F_{1}^{σ_{1}}

,...,

F_{n}^{σ_{n}}

} is a special covering for the set

S (f)

Recall that the literal

x_{i}^{α_{i}}

is included in all clauses of the subset

F_{i}^{α_{i}}

. Therefore, if

x_{i}^{α_{i}}

= 1, then the value of all clauses in

F_{i}^{α_{i}}

, is equal to 1, that is:

for any

i \in

[1,

n

] and

j \in

[1,

m

], if

x_{i}^{α_{i}}

= 1 and

e_{j} \in F_{i}^{α_{i}}

, then

e_{j}

= 1.

Therefore, if

σ_{1}

α_{1}

,...,

σ_{n}

α_{n}

, then

f

(

σ_{1}

,...,

σ_{n}

) = 1.

Comparing this with the results of Lemma 4.3, that is:

T_{1}

(

f_{n}

)

\in

n

m

) if and only if

f_{n} \in

CNF(

n

m

we obtain that

f_{n} \in

satCNF(

n

m

\nabla

Remark 4.4.1. According Proposition 3.2, the Turing machine

T_{CNF}

recognizes the strings of language CNF(

n

m

) in a polynomial time with respect to the length of string.

Let's for any natural numbers

n

and

m

, define the function

J_{1}

Σ^{*}

→

Σ^{*}

as follows:

J_{1}

(

w

) =

T_{CNF}

(w), if w

\in

CNF(

n

m

) and

J_{1}

(

w

) =

⟨ ε ▫ ε ⟩

, if w

\notin

CNF(

n

m

It is evident, that

J_{1}

is a polynomial time computable function

[2]

with computable time not exceeded the number

c ⨉ {| w |}^{2}

for certain constant

c

Also, it is evident, that for any string

w \in Σ^{*}

and for natural numbers

n

and

m

w \in

CNF

(n, m)

if and only if

J_{1}

(

w

)

\in

n

m

Recall, that

⟨ ε ▫ ε ⟩ \in Σ^{*}

and

⟨ ε ▫ ε ⟩ \notin

n

m

Theorem 4.5. For any natural numbers

n

and

m

satCNF(

n

m

)

\leq_{p}

sC(

n

m

Proof. It is obvious that satCNF(

n

m

) ⊆ CNF(

n

m

) and sC(

n

m

) ⊆ d(

n

m

By Lemma 4.2, the Turing machine

T_{1}

generates the string

T_{1}

(

f_{n}

) in polynomial time for any string

f_{n} \in CNF

(

n

m

). According to Theorem 4.4 and Remark 4.4.1, for any string

w

, and for any natural numbers

n

and

m

f_{n} \in

satCNF(

n

m

) if and only if

J_{1}

(

f_{n}

)

\in

sC(

n

m

Since

J_{1}

is a polynomial time computable function, then the language satCNF(

n

m

) is reduced polynomially to the language sC(

n

m

\nabla

Now let’s show that the problem of the existence of a special covering is polynomially reducible to the sat

CNF

problem. Let {

e_{1}

,...,

e_{m}

} be a nonempty set of

m

elements composed of the alphabet

Σ_{2}

as above. Let also ⟨

dS

⟩ be a string of the language

d

(

n

m

⟨dS⟩=⟨

M_{1}^{0}

▫

M_{1}^{1}

⋆...⋆

M_{n}^{0}

▫

M_{n}^{1}

⟩

\in

n

m

We form the string belonging to the language CNF(

n

m

), based on the string ⟨dS ⟩.

Let for any element

e_{j} \in S

L

(

e_{j}

) be the set of literals composed as follows:

L

(

e_{j}

) = {

x_{i}^{α_{i}}

/ (

i

∈[1,

n

]) & (

α_{i} \in \{0, 1\}

) & (

e_{j} \in

{

M_{i}^{α_{i}}

})}.

In addition, let l(

e_{i}

) be the clause formed by literals of the set L(

e_{i}

) and let

c

(

e_{i}

) be the string over the alphabet

Σ_{1}

, which forms by the set L(

e_{i}

c

(

e_{j}

) = ⟨

x_{i_{1}}^{α_{1}} x_{i_{2}}^{α_{2}}

...

x_{i_{k}}^{α_{k}}

⟩, where any literal belongs to the set L(

e_{j}

We compose the string ⟨

c

(

e_{1}

) ⋆

c

(

e_{2}

) ⋆... ⋆

c

(

e_{m}

) ⟩ over the alphabet

Σ_{1}

, which corresponds to the Boolean function in conjunctive normal form with

m

clauses, denoted by

g

(dS) =

⋀_{i = 1}^{m} l (e_{i})

It is easy to see, that as a result of formation of all clauses

c

(

e_{i}

), the number of literals

in clauses with pairwise different indexes will be equal to

n

. Therefore,

⟨

c

(

e_{1}

)⋆

c

(

e_{2}

)⋆...⋆

c

(

e_{m}

)⟩

\in

CNF(

n

m

Lemma 4.6. If ⟨dS ⟩ = ⟨

M_{1}^{0}

▫

M_{1}^{1}

⋆... ⋆

M_{n}^{0}

▫

M_{n}^{1}

⟩

\in

n

m

), then the string

⟨

c

(

e_{1}

)⋆...⋆

c

(

e_{m}

)⟩

is formed in polynomial time with respect to the length of the string ⟨dS ⟩.

Proof. Similar to the proof of Lemma 4.2, we describe the general workflow of a particular Turing machine, denoted by

T_{2}

, over the alphabet

Σ

, which time outputs the string

⟨

c

(

e_{1}

)⋆

c

(

e_{2}

)⋆...⋆

c

(

e_{m}

)⟩,

when input the string

⟨

M_{1}^{0}

▫

M_{1}^{1}

⋆...⋆

M_{n}^{0}

▫

M_{n}^{1}

⟩.

Let’s consider a Turing machine

T_{2}

, with input tape, output tape and two work tapes.

The general principles of

T_{2}

’s operation are as follows:

To form the clause

c

(

e_{i}

), it runs over the symbols of input data and with finding the element

e_{i}

included in

M_{j}^{α_{j}}

, adds the literal

x_{j}^{α_{j}}

to the literals forming the clause

c

(

e_{i}

) on the output tape.

At the first stage of work,

T_{2}

records pairs of indexes (j,

α_{j}

) of all subsets

M_{j}^{α_{j}}

on the first work tape in the same order in which the subsets are on the input tape.

The second stage of work consists of forming the clauses

c

(

e_{i}

) for i

\in

[1,

m

In order to generate a clause corresponding to the element

e_{i}

T_{2}

uses the second work tape, adding

e_{i}

on it and scanning

e_{i}

during the formation procedure

c

(

e_{i}

After recording the pairs (j,

α_{j}

T_{2}

starts work by recording

e_{1}

on the second work tape.

To determine each step of

T_{2}

it is enough to consider the configuration of three current scanned records on different tapes, which we denote by (

H_{1}

H_{2}

H_{3}

,):

H_{1}

is the scanned symbol on input tape,

H_{2}

is the scanned pair of indexes on the first work tape of considering subset,

H_{3}

is the scanned element on the second work tape, that is, the element

e_{i}

if the clause

c

(

e_{i}

) is forming.

The first configuration that will be considered to start working over the input data, is

(

e_{k}

, (

1

, 0),

e_{1}

where

e_{k}

is the first symbol of input data.

To form

c

(

e_{i}

), the Turing's machine

T_{2}

performs actions depending on configuration:

with configurations (ε, (

j

α_{j}

e_{i}

) or (

e_{k}

, (

j

α_{j}

e_{i}

), where

k \neq i

scans the next symbol on input tape.

with configuration (

e_{i}

, (

j

α_{j}

e_{i}

1) adds the literal

x_{j}^{α_{j}}

on output tape,

2) scans the next symbol on input tape.

with configuration (▫, (

j

, 0),

e_{i}

1) scans the next symbol on input tape,

2) scans the pair (

j

, 1) on the first work tape.

with configuration (⋆, (

j

, 1),

e_{i}

)

1) scans the next symbol on input tape,

2) scans the pair (

j

+1, 0) on the first work tape.

with configuration (end of input string, (

j

, 1),

e_{i}

) and

i

m

1) adds ⋆ to the output tape,

2) adds the symbol

e_{i + 1}

to the second work tape and scans it,

3) scans the first symbol of input tape,

4) scans the pair (

1

, 0) on the first tape,

5) starts to run over the input data again, to detect the element

e_{i + 1}

with configuration (end of input string, (

n

1

e_{m}

T_{2}

stops.

Obviously, on the output tape we will obtain the string

⟨

c

(

e_{1}

)⋆

c

(

e_{2}

)⋆...⋆

c

(

e_{m}

)⟩.

It is easy to see that the number of actions performed by

T_{2}

to complete the described procedure is polynomial with respect to the length |dS| of the string ⟨dS ⟩.

The number of mentioned actions does not exceed the number

c ⨉ {| dS |}^{2}

\nabla

Let's denote by

T_{2}

(dS) the string formed as a result of

T_{2}

's work on input ⟨dS ⟩:

T_{2}

(dS) =⟨

c

(

e_{1}

)⋆

c

(

e_{2}

)⋆...⋆

c

(

e_{m}

)⟩.

Obviously,

T_{2}

forms the string

T_{2}

(

dS

) based on the string ⟨dS ⟩ for any special decomposition

dS

of the set {

e_{1}

,...,

e_{m}

Theorem 4.7. For any natural numbers

n

and

m

⟨dS ⟩

\in

sC(

n

m

) if and only if

T_{2}

(dS)

\in

satCNF(

n

m

Proof. Let ⟨dS ⟩

\in

sC(

n

m

). This means that the total number of elements with pairwise different indexes in all subsets is equal to

m

. So, each of the elements

e_{1}

,...,

e_{m}

is included in some of subsets forming the string ⟨dS ⟩, and there is a Boolean tuple (

α_{1}

α_{2}

,...,

α_{n}

) such that

⋃_{i = 1}^{n} M_{i}^{α_{i}}

⋃_{i = 1}^{n} {(M}_{i}^{0} \cup M_{i}^{1})

This means that for any element

e_{i} \in ⋃_{i = 1}^{n} {(M}_{i}^{0} \cup M_{i}^{1})

, there exists a subset

M_{j}^{α_{j}}

∈ {

M_{1}^{α_{1}}

M_{2}^{α_{1}}

,...,

M_{n}^{α_{n}}

} such that

e_{i} \in M_{j}^{α_{j}}

On the other hand, if

e_{i} \in M_{j}^{α_{j}}

then

x_{j}^{α_{j}} \in

e_{i}

). Thus, the number of forming clauses will be

m

, which means that the number of strings corresponding to clauses also will be

m

Let's for simplicity denote by

g_{n}

T_{2}

(

dS

), that is

g_{n}

= ⟨

c

(

e_{1}

) ⋆

c

(

e_{2}

) ⋆... ⋆

c

(

e_{m}

) ⟩.

Also, we denote by

g

the function corresponding to the string

g_{n}

Since

x_{j}

α_{j}

implies

x_{j}^{α_{j}}

= 1, then (

σ_{1}

α_{1}

) &... & (

σ_{n}

α_{n}

) implies

g

(

σ_{1}

.

..,

σ_{n}

) =

g

(

dS

)(

σ_{1}

.

..,

σ_{n}

) =1.

Therefore,

T_{2}

(

dS

) = ⟨

c

(

e_{1}

) ⋆

c

(

e_{2}

) ⋆... ⋆

c

(

e_{m}

) ⟩

\in

satCNF(

n

m

Now suppose, that

T_{2}

(

dS

)

\in

sat

CNF

(

n

m

). That is,

g

is a satisfiable function, which means that for some Boolean tuple (

σ_{1}

,...,

σ_{n}

g

(

σ_{1}

σ_{2}

,...,

σ_{n}

) =1.

According to Theorem 4.4,

g_{n} \in

sat

CNF

(

n

m

) if and only

T_{1}

(

g_{n}

)

\in sC

(

n

m

Since

T_{1}

(

g_{n}

) = ⟨

G_{1}^{0}

▫

G_{1}^{1}

⋆... ⋆

G_{n}^{0}

▫

G_{n}^{1}

⟩, then for some Boolean tuple

σ_{1}

,...,

σ_{n}

, we obtain

⋃_{i = 1}^{n} G_{i}^{σ_{i}}

⋃_{i = 1}^{n} {(G}_{i}^{0} \cup G_{i}^{1})

This means that for any clause

l

(

e_{i}

), there exists a subset

G_{j}^{σ_{j}}

such that

G_{j}^{σ_{j}}

∈{

G_{1}^{σ_{1}}

G_{2}^{σ_{2}}

,...,

G_{n}^{σ_{n}}

} and

l

(

e_{i}

)∈

G_{j}^{σ_{j}}

But then

e_{i} \in M_{j}^{σ_{j}}

, because of definition of

G_{j}^{σ_{j}}

G_{j}^{σ_{j}}

= {

l

(

e_{k}

) /

l

(

e_{k}

) ∈

S

(

g

) and

l

(

e_{k}

) contains

x_{j}^{σ_{j}}

, (

k

∈ [1,

m

])}.

At the same time the clause

l

(

e_{i}

) contains the literal

x_{j}^{σ_{j}}

only if

e_{i} \in M_{j}^{σ_{j}}

Since any element

e_{i}

determines the composition of one clause, and any clause is defined by one element, then it is easy to prove that for any element

e_{i}

there exists a subset

M_{j}^{σ_{j}} \in

{

M_{1}^{σ_{1}}

M_{2}^{σ_{2}}

,...,

M_{n}^{σ_{n}}

} such, that

e_{i} \in M_{j}^{σ_{j}}

So,

⋃_{i = 1}^{n} M_{i}^{σ_{i}}

⋃_{i = 1}^{n} {(M}_{i}^{0} \cup M_{i}^{1})

Therefore, ⟨

M_{1}^{0}

▫

M_{1}^{1}

⋆... ⋆

M_{n}^{0}

▫

M_{n}^{1}

⟩

\in

sC(

n

m

\nabla

Remark 4.7.1. According Proposition 3.2, the Turing machine

T_{d}

recognizes the strings of language d(

n

m

) in a polynomial time with respect to the length of string. Мore precisely, this time is estimated as

c ⨉ {| w |}^{2}

, where

w

is an input string.

Let's for natural numbers

n

and

m

, define the function

J_{2}

Σ^{*}

→

Σ^{*}

as follows:

J_{2}

(

w

) =

T_{2}

(w), if w

\in

(n, m)

and

J_{2}

(

w

) = ⟨

ε

▫

ε

⟩ if

\notin

n

m

It is evident, that

J_{2}

is a polynomial time computable function with computable time not exceeded the number

c ⨉ {| w |}^{2}

for certain constant

c

It is also obvious that for any natural numbers

n

and

m

, and for any string

w \in Σ^{*}

w \in d (n, m)

if and only if

J_{2}

(

w

)

\in

CNF

(n, m)

Recall, that

⟨ ε ▫ ε ⟩ \in Σ^{*}

and

⟨ ε ▫ ε ⟩ \notin d

(

n

m

Theorem 4.8. For any natural numbers

n

and

m

, sC(

n

m

)

\leq_{p}

satCNF(

n

m

Proof. It is obvious that sC(

n

m

) ⊆ d(

n

m

) and satCNF(

n

m

) ⊆ CNF(

n

m

According to Lemma 4.6, for any natural numbers

n

and

m

, there is a Turing's machine

T_{2}

, which for any string

⟨dS⟩=⟨

M_{1}^{0}

▫

M_{1}^{1}

⋆...⋆

M_{n}^{0}

▫

M_{n}^{1}

⟩

\in

n

m

)

forms the string

T_{2}

(

dS

) =⟨

c

(

e_{1}

)⋆

c

(

e_{2}

)⋆...⋆

c

(

e_{m}

)⟩

in polynomial time with respect to the length of string ⟨

dS

⟩. According to the Theorem 4.7 and Remark 4.7.1, for any string

w

, and for any natural numbers

n

and

m

⟨dS ⟩

\in

sC(

n

m

) if and only if

J_{2}

(dS )

\in

satCNF(

n

m

Therefore, sC(

n

m

)

\leq_{p}

satCNF(

n

m

Since

J_{2}

is a polynomial time computable function, then the language sC(

n

m

) is polynomially reduced to the language satCNF (

n

m

\nabla

Theorem 4.9. For any natural numbers

n

and

m

, the language satCNF (

n

m

) and the language sC(

n

m

) are polynomially equivalent.

Proof. Follows of Theorems 4.5 and 4.8.

Corollary 4.9.1 The problem of existence of a special covering is an

NP

-complete problem.

Proof. Follows from the Theorem 4.9.

\nabla

The theorem 4.9 gives us possibility to use the concept of special decomposition when discuss the questions concerning to satisfiability of a function. That is, instead of investigating questions related to the satisfiability a given function in con_junctive normal form, we can investigate corresponding questions related to the existent of a special covering for the set of clauses under a special decomposition of this set.

5. Replaceability of Subsets

In this section, to study important properties of special decompositions, we introduce a new concept called replaceable subsets.

Let

S

= {

e_{1}

,...,

e_{m}

} be a nonempty set, and let for some Boolean tuple (

α_{1}

,...,

α_{n}

M_{1}^{α_{1}}

M_{1}^{{\overset{̅}{α}}_{1}}

,...,

M_{n}^{α_{n}}

M_{n}^{{\overset{̅}{α}}_{n}}

be arbitrary subsets of the set

S

such that the set

d_{n} S

{(M_{1}^{α_{1}}

M_{1}^{{\overset{̅}{α}}_{1}})

,..., (

M_{n}^{α_{n}}

M_{n}^{{\overset{̅}{α}}_{n}}

)}

is a special decomposition of the set

S

Recall that in this case

{sM}^{0}

= {

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}

} and

{sM}^{1}

= {

M_{1}^{{\overset{̅}{α}}_{1}}

,...,

M_{n}^{{\overset{̅}{α}}_{n}}

Definition 5.1. If for some

α

∈ {0,1}, the set of

α

-components of the special decomposition

d_{n} S

covers the set

S

, then it will be called a special

s M^{α}

-covering for the set

S

According to Lemm 1.5 in

[13]

, there exists a special covering for the set

S

under the decomposition

d_{n} S

if and only if for some

α

∈ {0,1} there exists an

{sM}^{α}

-covering for the set

S

under some special decomposition

I (d_{n} S)

. The search for an

{sM}^{0}

-covering in a decomposition

d_{n} S

consists of finding ordered pairs such that, by permuting their components, the missing elements of the

0

-domain are moved to the

0

-domain.

Obviously, if the 0-domain of some special decomposition covers the set

S

, then permutating the components of all ordered pairs of this decomposition, we obtain

{sM}^{1}

-covering under another special decomposition and vice versa. So, the notation

s M^{α}

-covering, will mean that

α

∈ {0, 1}.

Definition 5.2. Let

d_{n} S

be a special decomposition of a set

S

such that

M_{i}^{α_{i}} \in s M^{0}

and the

0

-domain of the decomposition does not cover the set

S

1) We say that the subset

M_{i}^{α_{i}}

is an immediate

{sM}^{0}

-replaceable subset, if

M^{0} \subseteq

(

i

)

M^{0}

2) We say that

M_{i}^{α_{i}}

is an

{sM}^{0}

-replaceable subset if it is an immediate

{sM}^{0}

-replaceable or, if

d_{n} S

contains ordered pairs (let

i_{1}

,...,

i_{k}

be their indices) such that

M^{0} \subseteq

(

i

i_{1}

,...,

i_{k}

)

M^{0}

3) We say that

e \in S

is an

{sM}^{0}

-reachable element if there is an ordered pair (

M_{i}^{α_{i}}

M_{i}^{{\overset{̅}{α}}_{i}}

) such that

(

M_{i}^{α_{i}} \in s M^{0}

) & (

e

∉

M^{0}

)

(

e

∈

M_{i}^{{\overset{̅}{α}}_{i}}

), and

M_{i}^{α}

is an

{sM}^{0}

-replaceable subset. We will also say that the element

e

is associated with

s M^{α}

-replaceability of the subset

M_{i}^{α_{i}}

The essence of the concept of

s M^{α}

-replaceability is to perform permutations of the components of some ordered pairs, as a result of which the

α

-domain receives a new element without losing its own elements. It is easy to see the

M^{α}

-replacement of a subset is an

I

-transformation of the given decomposition. Therefore, according to the Lemma 1.5 in

[13]

, for any special decomposition, as a result of any replacement, we obtain a new special decomposition.

Theorem 5.3. Let for some Boolean tuples (

τ_{1}

,...,

τ_{n}

) and (

α_{1}

,...,

α_{n}

), the set

c_{n}

S= {

M_{1}^{τ_{1}}

,...,

M_{i}^{τ_{i}}

,...,

M_{n}^{τ_{n}}}

be a special covering for the set S under the special decomposition

d_{n} S

d_{n}

{(M_{1}^{α_{1}}

M_{1}^{{\overset{̅}{α}}_{1}})

,..., (

M_{n}^{α_{n}}

M_{n}^{{\overset{̅}{α}}_{n}}

)}.

Then, for any

i \in

[1,

n

], the subset

M_{i}^{{\overset{̅}{τ}}_{i}}

is an

s M^{{\overset{̅}{τ}}_{i}}

-replaceable subset.

Proof. For any

i \in

[1,

n

], if

M^{{\overset{̅}{τ}}_{i}} \subseteq

(

i

)

M^{{\overset{̅}{τ}}_{i}}

, then

M^{{\overset{̅}{τ}}_{i}}

is an immediate

s M^{{\overset{̅}{τ}}_{i}}

-replaceable subset. Suppose that for some

i \in

[1,

n

], the subset

M_{i}^{{\overset{̅}{τ}}_{i}}

contains elements that are not included in other subsets of the

{\overset{̅}{τ}}_{i}

-domain. Since

c_{n} S

is a special covering for the set

S

, then obviously, for any element

e \in M_{i}^{{\overset{̅}{τ}}_{i}}

there is a subset

M_{j}^{τ_{j}}

such that (

M_{j}^{τ_{j}} \in c_{n} S

) &

(e \in M_{j}^{γ_{j}})

Suppose that for some

γ_{1}

,...,

γ_{k} \in

{0, 1},

M_{i_{1}}^{γ_{1}}

,...,

M_{i_{k}}^{γ_{k}}

are the subsets such that

({

M_{i_{1}}^{γ_{1}}

,...,

M_{i_{k}}^{γ_{k}}

}

\subseteq c_{n} S

) & (

M_{i}^{{\overset{̅}{τ}}_{i}} \subseteq ⋃_{j = 1}^{k} M_{i_{j}}^{τ_{j}})

It is obvious that some of these subsets are included in the

τ_{i}

-domain, since by assumption,

M_{i}^{{\overset{̅}{τ}}_{i}}

is not immediate replaceable subset. Let them be the subsets

M_{j_{1}}^{β_{1}}

,...,

M_{j_{l}}^{β_{l}}

. That is,

({

M_{j_{1}}^{β_{1}}

,...,

M_{j_{l}}^{β_{l}}

}

\subseteq c_{n} S

)& ({

M_{j_{1}}^{β_{1}}

,...,

M_{j_{l}}^{β_{l}}

}

\subseteq s M_{i}^{τ_{i}}

Let’s consider the case, when

τ_{i}

α_{i}

. For

τ_{i}

{\overset{̅}{α}}_{i}

, will be a similar proof. In this case, the ordered pair

(M_{i}^{τ_{i}}

M_{i}^{{\overset{̅}{τ}}_{i}}) \in d_{n} S

is the same as

(M_{i}^{α_{i}}

M_{i}^{{\overset{̅}{α}}_{i}})

. But then {

M_{j_{1}}^{β_{1}}

,...,

M_{j_{l}}^{β_{l}}

}

\subseteq s M_{i}^{α_{i}}

Therefore, the subsets

M_{j_{1}}^{β_{1}}

,...,

M_{j_{l}}^{β_{l}}

are moved to the

{\overset{̅}{τ}}_{i}

-domain by permutations of the components of the ordered pairs

(M_{i}^{α_{i}}

M_{i}^{{\overset{̅}{α}}_{i}})

(M_{j_{1}}^{β_{1}}, M_{j_{1}}^{{\overset{̅}{β}}_{1}})

,...,

(M_{j_{l}}^{β_{l}}, M_{j_{l}}^{{\overset{̅}{β}}_{l}})

If some of the subsets

M_{j_{1}}^{{\overset{̅}{β}}_{1}}

,...,

M_{j_{l}}^{{\overset{̅}{β}}_{l}}

contain elements that are not included in other subsets in the

{\overset{̅}{τ}}_{i}

-domain, then by the same reasoning as for the subset

M_{i}^{{\overset{̅}{τ}}_{i}}

, we find the corresponding ordered pairs and perform permutations of their components.

Since as a result of all permutations new subsets included in

c_{n} S

move into the

{\overset{̅}{τ}}_{i}

-domain, this domain will not lose elements. Therefore,

M_{i}^{{\overset{̅}{τ}}_{i}}

is an

{sM}^{{\overset{̅}{τ}}_{i}}

-replaceable subset.

\nabla

Corollary 5.3.1. Let a special decomposition

d_{n} S

of the set

S

be given such that some element

e \in S

is not included in the

α

-domain of this decomposition,

e

∉

M^{α}

e

is not an s

M^{α}

-reachable element, then there is no special covering of the set

S

under the decomposition of

d_{n} S

Proof. Follows directly from Theorem 5.3.

\nabla

Corollary 5.3.2. If there exists a special covering for the set

S

under the decomposition

d_{n} S

, then for any

i \in

[1,

n

] the following is true:

the subset

M_{i}^{0}

is s

M^{0}

-replaceable or the subset

M_{i}^{1}

s M^{1}

-replaceable.

Proof. Let for some Boolean tuple (

α_{1}

α_{2}

,...,

α_{n}

), the set

c_{n}

S = {

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}}

be a special covering for the set

S

. Obviously, the conditions of Theorem 4.2 are satisfied. So,

for

α_{i}

= 0, then the subset

M_{i}^{1}

is an

s M^{1}

-replaceable subset,

for

α_{i}

= 1, then the subset

M_{i}^{0}

is an s

M^{0}

-replaceable subset. ∇

In search of

s M^{0}

-reachability of an element

e \in

S such that (

e

∉

M^{0}

)

(

e

∈

M_{i}^{{\overset{̅}{α}}_{i}}

), we look for ordered pairs that ensure this reachability. At the same time, an important question arises when studying the existence of a special covering for a set.

Let {

e_{q_{1}}

,...,

e_{q_{l}}

}

= S

M^{0}

. The elements

e_{q_{1}}

,...,

e_{q_{l}}

can occur in different subsets in the

1

-domain of the decomposition

d_{n}

S. So, to find a special covering for the set

S

, we can perform a sequential search for

s M^{0}

-reachability of each element of the set {

e_{q_{1}}

,...,

e_{q_{l}}

1) search for ordered pairs that will ensure the s

M^{0}

-reachability of an element included in the set {

e_{q_{1}}

,...,

e_{q_{l}}

} under the decomposition

d_{n}

S, and, having found them, permute their components. The result will be a new special decomposition.

2) we perform the same procedure for some other element of the set {

e_{q_{1}}

,...,

e_{q_{l}}

} under the new decomposition and continue the similar procedure for all elements.

Let’s find out whether finding a special covering depends on the order in which the missing elements are considered.

Definition 5.4. Let we are given a special decomposition

d_{n}

S of the set S. For an ordered set {

e_{i_{1}}

,...,

e_{i_{l}}

}

\subseteq

S, we define a decomposition denoted by

{d_{n} S}^{0}

(

e_{i_{1}}

,...,

e_{i_{l}}

(i) if

e_{i_{1}} \in M^{0}

, then

{d_{n} S}^{0} (e_{i_{1}})

coincides with the decomposition

d_{n}

(ii) if

e_{i_{1}} \notin M^{0}

, then we consider the following two cases:

(ii.1)

e_{i_{1}}

is an s

M^{0}

-reachable element under the decomposition

d_{n}

In this case,

{d_{n} S}^{0}

(

e_{i_{1}}

) is defined as a decomposition obtained by permuting the components of the ordered pairs that ensure this reachability.

(ii.2)

e_{i_{1}}

is not an s

M^{0}

-reachable element under the decomposition

d_{n}

In this case, we consider the resulting decomposition as an empty set,

{d_{n} S}^{0} (e_{i_{1}})

= ∅.

(iii) let for some 1

\leq

k < l,

{d_{n} S}^{0}

(

e_{i_{1}}

,...,

e_{i_{k}}

)

\neq \emptyset

If the element

e_{i_{k + 1}}

is included in the

0

-domain of this decomposition, then the decomposition

{d_{n} S}^{0}

(

e_{i_{1}}

,...,

e_{i_{k}}, e_{i_{k + 1}}

) coincides with the decomposition

{d_{n} S}^{α} (e_{i_{1}}

,...,

e_{i_{k}})

e_{i_{k + 1}}

is not included in the

α

-domain of the decomposition

{d_{n} S}^{0}

(

e_{i_{1}}

,...,

e_{i_{k}}

), then we consider the following two cases:

(iii.1)

e_{i_{k + 1}}

is an s

M^{0}

-reachable element under the decomposition

{d_{n} S}^{0}

(

e_{i_{1}}

,...,

e_{i_{k}}

In this case,

{d_{n} S}^{0}

(

e_{i_{1}}

,...,

e_{i_{k}}, e_{i_{k + 1}}

) is defined as a decomposition that is obtained by permuting the components of ordered pairs that ensure this reachability.

(iii.2)

e_{i_{k + 1}}

is not an s

M^{0}

-reachable element under the decomposition

{d_{n} S}^{0}

(

e_{i_{1}}

,...,

e_{i_{k}}

). In this case, we will consider the decomposition

{d_{n} S}^{0}

(

e_{i_{1}}

,...,

e_{i_{k}}

e_{i_{k + 1}}

) as an empty set.

(iv) if for some 1

\leq

<

{d_{n} S}^{0}

(

e_{i_{1}}

,...,

e_{i_{k}}

) = ∅, then also,

{d_{n} S}^{0}

(

e_{i_{1}}

,...,

e_{i_{k}}

e_{i_{k + 1}}

) = ∅.

Theorem 5.5. Let the special decomposition

d_{n} S

of the set

S

be given such that

{

e_{q_{1}}

,...,

e_{q_{l}}

}

=

S \

M^{0}

(i) if there exists a special covering for the set

S

under the special decomposition

d_{n} S

, and {

e_{j_{1}}

,...,

e_{j_{l}}

} is an arbitrary permutation of the elements of the set {

e_{q_{1}}

,...,

e_{q_{l}}

}, then:

(a)

{d_{n} S}^{0} (e_{j_{1}}

,...,

e_{j_{l}}) \neq \emptyset

(b) the

0

-domain of the decomposition

{d_{n} S}^{0} (e_{j_{1}}

,...,

e_{j_{l}})

is an s

M^{0}

-covering for S.

(ii) if

{d_{n} S}^{0} (e_{j_{1}}

,...,

e_{j_{k}})

= ∅ for an arbitrary ordered set {

e_{j_{1}}

,...,

e_{j_{k}}

} consisting of some elements of the set {

e_{q_{1}}

,...,

e_{q_{l}}

}, then there does not exist a special covering for the set S under the decomposition

d_{n}

Proof. (i) Let for some Boolean tuple (

α_{1}

,...,

α_{n}

), the set

c_{n}

S = {

M_{1}^{α_{1}}

,...,

M_{n}^{α_{n}}

} be a special covering for the set

S

under the decomposition

d_{n}

S. The condition S \

M^{0}

= {

e_{q_{1}}

,...,

e_{q_{l}}

} implies that

c_{n}

\neq

M^{0}

and {

e_{q_{1}}

,...,

e_{q_{l}}

}

\subseteq M^{1}

. Therefore, for any

e_{q_{j}} \in

{

e_{q_{1}}

,...,

e_{q_{l}}

}, there is a subset included in

c_{n}

S, which contains the element

e_{q_{j}}

Let

M_{i_{1}}^{{\overset{̅}{τ}}_{1}}

,...,

M_{i_{k}}^{{\overset{̅}{τ}}_{k}}

, be subsets such that the elements of the set {

e_{q_{1}}

,...,

e_{q_{l}}

} are located these subsets, where {

τ_{1}

,...,

τ_{k}

}

\in

{

α_{1}

,...,

α_{n}

}. In addition,

({

M_{i_{1}}^{{\overset{̅}{τ}}_{1}}

,...,

M_{i_{k}}^{{\overset{̅}{τ}}_{k}}

}

\subseteq M^{1}

) & (

M_{i_{1}}^{{\overset{̅}{τ}}_{1}}

,...,

M_{i_{k}}^{{\overset{̅}{τ}}_{k}} \in c_{n}

S).

Let for some {

τ_{1}

,...,

τ_{k}

}

\in

{

α_{1}

,...,

α_{n}

}, all elements of the set {

e_{q_{1}}

,...,

e_{q_{l}}

} be located in the subsets

M_{i_{1}}^{{\overset{̅}{τ}}_{1}}

,...,

M_{i_{k}}^{{\overset{̅}{τ}}_{k}}

, in addition,

({

M_{i_{1}}^{{\overset{̅}{τ}}_{1}}

,...,

M_{i_{k}}^{{\overset{̅}{τ}}_{k}}

}

\subseteq M^{1}

) & (

M_{i_{1}}^{{\overset{̅}{τ}}_{1}}

,...,

M_{i_{k}}^{{\overset{̅}{τ}}_{k}} \in c_{n}

S).

It is easy to see that for any subset

M_{i_{j}}^{{\overset{̅}{τ}}_{j}} \in

{

M_{i_{1}}^{{\overset{̅}{τ}}_{1}}

,...,

M_{i_{k}}^{{\overset{̅}{τ}}_{k}}

} the conditions of Theorem 5.3 are satisfied, which means that the subset

M_{i_{j}}^{τ_{j}}

{sM}^{0}

-replaceable. Without limiting the generality of the reasoning, we can assume that

e_{j_{1}} \in M_{i_{1}}^{{\overset{̅}{τ}}_{1}}

. So, as a result of

{sM}^{0}

-replacement of the subset

M_{i_{j}}^{τ_{j}}

, we obtain the special decomposition

{d_{n} S}^{0} (e_{j_{1}}) \neq

∅.

Since the transition from the decomposition

d_{n} S

to the decomposition

{d_{n} S}^{0} (e_{j_{1}})

is an

I

-transformation, then according to Lemma 1.5 in

[13]

, there exists a special covering for

S

under the decomposition

{d_{n} S}^{0}

(

e_{j_{1}}

). If the element

e_{j_{2}}

has moved to the

0

-domain as a result of an

{sM}^{0}

-replacement associated with the element

e_{j_{1}}

, then according to Definition 5.4,

{d_{n} S}^{0} (e_{j_{1}}

) =

{d_{n} S}^{0} (e_{j_{1},} e_{j_{2}})

and

{d_{n} S}^{0} (e_{j_{1}}, e_{j_{2}}) \neq \emptyset

e_{j_{2}}

has not moved to the 0-domain, then by the same reasoning as in the case of the element

e_{j_{1}}

, there exists a subset

M_{i_{s}}^{{\overset{̅}{τ}}_{s}}

such, that (

M_{i_{s}}^{{\overset{̅}{τ}}_{s}} \in c_{n}

S) & (

e_{j_{2}} \in M_{i_{s}}^{{\overset{̅}{τ}}_{s}})

By Theorem 5.3, the subset

M_{i_{s}}^{τ_{s}}

{sM}^{0}

-replaceable. Since the replacement is associated with the element

e_{j_{2}}

, then performing the

M^{α}

-replacement of the subset

M_{i_{s}}^{τ_{s}}

, we obtain:

{d_{n} S}^{0} (e_{j_{1}}, e_{j_{2}}) \neq

∅,

{d_{n} S}^{0} (e_{j_{1}}, e_{j_{2}})

is a special decomposition,

3) there is a special covering for the set

S

under the decomposition

{d_{n} S}^{0} (e_{j_{1}}, e_{j_{2}})

Repeating the similar procedure, no more than

l

times, we obtain:

{d_{n} S}^{0} (e_{j_{1}}

,...,

e_{j_{l}}) \neq

∅,

{d_{n} S}^{0} (e_{j_{1}}

,...,

e_{j_{l}})

is a special decomposition,

3) there is a special covering for the set

S

under the decomposition

{d_{n} S}^{0} (e_{j_{1}}

,...,

e_{j_{l}})

It is obvious that when forming the decomposition

{d_{n} S}^{0} (e_{j_{1}}

,...,

e_{j_{l}})

all elements of the set {

e_{j_{1}}

,...,

e_{j_{l}}

} move into its 0-domain. At the same time, the 0-domain of the corresponding decomposition does not lose elements at any stage. Therefore, the

0

-domain of the decomposition

{d_{n} S}^{0} (e_{j_{1}}

,...,

e_{j_{l}})

is an

s M^{0}

-covering for the set

S

(ii) Now let {

e_{j_{1}}

,...,

e_{j_{k}}

}, where

k \leq l

, be an ordered set obtained by an arbitrary permutation of arbitrary elements of the set {

e_{q_{1}}

,...,

e_{q_{l}}

}, such that that

{d_{n} S}^{0}

(

e_{j_{1}}

,...,

e_{j_{k}})

= ∅.

Recall, that

{d_{n} S}^{0}

(

e_{j_{1}}

,...,

e_{j_{k}})

= ∅ in the following cases:

(ii.1)

{d_{n} S}^{0}

(

e_{j_{1}}

) = ∅. This means, that under the decomposition

d_{n} S

there does not exist

{sM}^{0}

-replaceable subset, associated with

e_{j_{1}}

so, there does not exist a special covering for S.

(ii.2) for some element

e_{j_{r}} (

1 ≤

r

k)

{d_{n} S}^{0}

(

e_{j_{1}}

,...,

e_{j_{r}}) \neq

∅

{d_{n} S}^{0} (e_{j_{1}}

,...,

e_{j_{r}}

e_{j_{r + 1}})

= ∅.

This means that under the decomposition

{d_{n} S}^{0}

(

e_{j_{1}}

,...,

e_{j_{r}})

, there does not exist an

{sM}^{0}

-replaceable subset associated with the element

e_{j_{r + 1}}

. But then, by Corollary 4.2.1, there cannot exist a special covering for the set

S

under the decomposition

{d_{n} S}^{0}

(

e_{j_{1}}

,...,

e_{j_{r}})

. Since the decomposition

{d_{n} S}^{0}

(

e_{j_{1}}

,...,

e_{j_{r}})

is obtained as a result of an

I

-transformation of the decomposition

d_{n} S

, then by Lemma 1.5 in

[13]

, the decomposition

d_{n} S

does not allow a special covering for the set S. ∇

6. Applications

Let S

(f)

= {

c_{1}

,...,

c_{m}

} be the set of clauses the Boolean function

f

(

x_{1}

,...,

x_{n}

), and let

d_{n}

f

)) ={(

F_{1}^{0}

F_{1}^{1}

),..., (

F_{n}^{0}

F_{n}^{1}

)}

be special decomposition of the set S

(f)

For a subset

S_{1}

(

f

)

\subseteq

(f)

and

S_{1}

(

f

)

\neq

∅, we say that

S_{1}

(

f

) is a satisfiable subset if there exists a Boolean assignment tuple (

α_{1}

,...,

α_{n}

), such that every clause included in

S_{1}

(

f

) evaluates to 1 when assigning values

α_{1}

,...,

α_{n}

to variables

x_{1}

,...,

x_{n}

Theorem 6.1. Let (

x_{1}

,...,

x_{n}

) be a function represented in conjunctive normal form with

m

clauses, and let

d_{n} S (f

) be a special decomposition of the set S

(f

Then, as a result of any

I

-transformation of the decomposition

d_{n}

f

), the set of clauses S

(f

) is divided into two satisfiable subsets.

Proof. Let for some Boolean tuple (

σ_{1}

,...,

σ_{n}

), the set

(r_{1}

,...,

r_{p}

)I (

d_{n}

f

)) = {(

F_{1}^{σ_{1}}

F_{1}^{{\overset{̅}{σ}}_{1}}

),..., (

F_{n}^{σ_{n}}

F_{n}^{{\overset{̅}{σ}}_{n}}

)}

be an

I

-transformation of the decomposition

d_{n}

f

). Then,

σ_{1}

,...,

σ_{n}

will be as follows:

σ_{i}

= 0, if

i \notin

{

r_{1}

,...,

r_{p}

} and

σ_{i}

= 1, if

i \in

{

r_{1}

,...,

r_{p}

Consider an arbitrary subset in the

0

-domain of this decomposition

F_{k}^{σ_{k}}

∈ {

F_{1}^{σ_{1}}

,...,

F_{n}^{σ_{n}}

}

and the clauses included in it. By definition

F_{k}^{σ_{k}}

= {

c_{j}

c_{j}

∈ S(

f

) and

c_{j}

contains the literal

x_{k}^{σ_{k}}

j

∈ [1,

m

]}.

Obviously, if

x_{k}

σ_{k}

then all clauses in the subset

F_{k}^{σ_{k}}

will take the value 1. So, if

x_{1}

σ_{1}

,...,

x_{n}

σ_{n}

, then the set of clauses included in the 0-domain of this decomposition will be satisfiable.

It is easy to see that by the same reasoning as for the 0-domain, (

{\overset{̅}{σ}}_{1}

,...,

{\overset{̅}{σ}}_{n}

) will be the satisfying tuple for the 1-domain. Obviously, if

S_{0}

(

f

) and

S_{1}

(

f

) denote the sets of clauses included in the 0-domain and 1-domain, respectively, then S

(f)

S_{0}

(

f

)

\cup S_{1}

(

f

). ∇

Remark 6.2. Recall that any Boolean function in conjunctive normal form generates a special decomposition of the set of its clauses, and any special decomposition of a set generates a Boolean function represented in conjunctive normal form. In sec. 6 in

[13]

is shown that by permuting the components of an ordered pair, new function is generated.

Let

d_{n}

f

) be a special decomposition generated by the function

f

(

x_{1}

,...,

x_{n}

). Consider an ordered pair (

F_{i}^{0}

F_{i}^{1}

) ∈

d_{n}

f

), assuming that

F_{i}^{0}

= {

c_{l_{1}}

,...,

c_{l_{p}}

}and

F_{i}^{1}

= {

c_{j_{1}}

,...,

c_{j_{q}}

By the definition of these subsets,

1) the literal

{\overset{̅}{x}}_{i}

is included in all clauses of the set {

c_{l_{1}}

,...,

c_{l_{p}}

2) the literal

x_{i}

is included in all clauses of the set {

c_{j_{1}}

,...,

c_{j_{q}}

3) the literals

{\overset{̅}{x}}_{i}

and

x_{i}

are not included in any other clauses.

When permuting the components of the ordered pair (

F_{i}^{0}

F_{i}^{1}

), we obtain the special decomposition (

i

)

I

(

d_{n} S

(

f

)), in which the

i

-th ordered pair has the form (

F_{i}^{1}

F_{i}^{0}

). The remaining ordered pairs coincide with the corresponding ordered pairs of

d_{n} S

(

f

(

i

)

I

(

d_{n}

f

)) ={(

F_{1}^{0}

F_{1}^{1}

),..., (

F_{i}^{1}

F_{i}^{0}

),..., (

F_{n}^{0}

F_{n}^{1}

)}.

We form a function denoted as (

i

)

h^{I} (x_{1}

,...,

x_{n}

) in accordance with Section 3 based on the special decomposition (

i

)

I

(

d_{n}

f

)). Recall that if

d_{n}

S = {(

M_{1}^{0}

M_{1}^{1}

),..., (

M_{n}^{0}

M_{n}^{1}

)}

is a special decomposition of a set S = {

e_{1}

,...,

e_{m}

}, then for any element

e_{j}

∈ {

e_{1}

,...,

e_{m}

}, the clause

c

(

e_{j}

) will formed by the following set of literals, {

x_{i}^{α_{i}}

e_{j} \in M_{i}^{α_{i}}

}. Respectively,

(

i

)

h^{I} (x_{1}

,...,

x_{n}

) =

⋀_{j = 1}^{m} c (e_{j})

The ordered sets

d_{n} S

(

f

)) and (

i

)

I

(

d_{n}

f

)) differ only in the

i

-th ordered pair. That is,

F_{i}^{0}

= {

c_{l_{1}}

,...,

c_{l_{p}}

} is located in the 1-domain,

F_{i}^{1}

= {

c_{j_{1}}

,...,

c_{j_{q}}

} is located in the

0

-domain, of the resulting decomposition.

Let’s denote by

c_{1}^{'}

,...,

c_{m}^{'}

the clauses of the function

h^{I}

(

x_{1}

,...,

x_{n}

). That is,

S

(

h^{I}

) = {

c_{1}^{'}

,...,

c_{m}^{'}

Since

h^{I}

(

x_{1}

,...,

x_{n}

) is generated by the decomposition (

i

)

I

(

d_{n} S

(

f

)), then:

1) for any

c_{j_{r}}

∈ {

c_{j_{1}}

,...,

c_{j_{q}}

}, the corresponding new clause

c_{j_{r}}^{'}

will contain the literal

{\overset{̅}{x}}_{i}

2) for any

c_{l_{r}}

∈ {

c_{l_{1}}

,...,

c_{l_{p}}

}, the corresponding new clause

c_{l_{r}}^{'}

will contain the literal

x_{i}

Let

d_{n}

h^{I}

) = {(

H_{1}^{0}

H_{1}^{1}

),..., (

H_{n}^{0}

H_{n}^{1}

)} denotes the special decomposition (

i

)

I

(

d_{n}

f

)). According to the formation procedure of the function

h^{I}

(

x_{1}

,...,

x_{n}

), we obtain:

1) the literal

{\overset{̅}{x}}_{i}

is included in any of the clauses included in

H_{i}^{0}

2) the literal

x_{i}

is included in any of the clauses included in

H_{i}^{1}

At the same time, the clauses of the function (

i

)

h^{I}

(

x_{1}

,...,

x_{n}

), not included in the subsets

H_{i}^{0}

H_{i}^{1}

, coincide with the corresponding clauses of the function

f

(

x_{1}

,...,

x_{n}

). Thus, the function

h^{I}

(

x_{1}

,...,

x_{n}

) is obtained by replacing the literal

{\overset{̅}{x}}_{i}

with the literal

x_{i}

and the literal

x_{i}

with the literal

{\overset{̅}{x}}_{i}

in all clauses of the function

f

(

x_{1}

,...,

x_{n}

) containing these literals.

We will say that the function (

i

)

h^{I} (x_{1}

,...,

x_{n}

) is obtained by inverting the literals of the variable

x_{i}

in the function

f

(

x_{1}

,...,

x_{n}

Similarly, the expression (

i_{1}

,...,

i_{k}

)

h^{I}

(

x_{1}

,...,

x_{n}

) will mean the function generated by the decomposition (

i_{1}

,...,

i_{k}

)

I

(

d_{n}

f

)), for any

i_{1}

,...,

i_{k} \in

[1,

n

Theorem 6.3. A function

f

(

x_{1}

,...,

x_{n}

) represented in conjunctive normal form is satisfiable if and only if the function (

i_{1}

,...,

i_{k}

)

h^{I}

(

x_{1}

,...,

x_{n}

) is satisfiable.

Proof. Let

d_{n} S

(

f

)) = {(

F_{1}^{0}

F_{1}^{1}

),..., (

F_{n}^{0}

F_{n}^{1}

)} be a special decomposition of the set

S (f)

. Consider the special decomposition (

i_{1}

,...,

i_{k}

)

I

(

d_{n} S

(

f

)). By definition,

(

i_{1}

,...,

i_{k}

)

I

(

d_{n}

(f)

)) = {(

F_{1}^{σ_{1}}

F_{1}^{{\overset{̅}{σ}}_{1}}

),..., (

F_{n}^{σ_{n}}

F_{n}^{{\overset{̅}{σ}}_{n}}

)},

(

σ_{i}

= 0, if

i

∉ {

i_{1}

,...,

i_{k}

} and

σ_{i}

= 1, if

i \in

{

i_{1}

,...,

i_{k}

}).

Suppose that the

f

(

x_{1}

,...,

x_{n}

) is a satisfiable function, that is, there exists a Boolean tuple (

α_{1}

,...,

α_{n}

) such that

f

(

α_{1}

,...,

α_{n}

) = 1. Using the arguments of Remark 6.2 regarding the inversion of literals, it is easy to see that the function {

i_{1}

,...,

i_{k}

}

h^{I}

(

x_{1}

,...,

x_{n}

) will be satisfiable by the assignment tuple (

β_{1}

,...,

β_{n}

) if we define this tuple as follows:

β_{i}

α_{i}

, if

i

∉ {

i_{1}

,...,

i_{k}

} and

β_{i}

{\overset{̅}{α}}_{1}

, if

i \in

{

i_{1}

,...,

i_{k}

That is, {

i_{1}

,...,

i_{k}

}

h^{I}

(

β_{1}

,...,

β_{n}

) = 1.

Obviously, the opposite is also true.

If {

i_{1}

,...,

i_{k}

}

h^{I}

(

β_{1}

,...,

β_{n}

) = 1 for some Boolean assignment tuple (

β_{1}

,...,

β_{n}

) then there is a tuple (

α_{1}

,...,

α_{n}

) such that f(

α_{1}

,...,

α_{n}

) = 1. ∇

Definition 6.4. A conjunctive normal form of a Boolean function will be called a Proportional Conjunctive Normal Form, if each clause contains at least one negative literal or if each clause contains at least one positive literal.

Theorem 6.5. A Boolean function

f

(

x_{1}

,...,

x_{n}

) represented in conjunctive normal form is satisfiable if and only if it can be transformed into a function in Proportional conjunctive normal form using literal inversions.

Proof. Let the ordered set

d_{n}

f

)) = {(

F_{1}^{0}

F_{1}^{1}

),..., (

F_{n}^{0}

F_{n}^{1}

)} be a special decomposition of the set of clauses S

(f)

of the function

f

(

x_{1}

,...,

x_{n}

One part of the theorem is obvious. Suppose that the function is transformed into a function represented in Proportional conjunctive normal form using literal inversions. Let it be the function

h^{I} (x_{1}

,...,

x_{n}

). It is easy to notice, that a function in proportional conjunctive normal form is satisfiable, so by the Theorem 6.3, the function

f

(

x_{1}

,...,

x_{n}

) is satisfiable.

The opposite: Let

f

(

x_{1}

,...,

x_{n}

) be a satisfiable function. Then, there is a Boolean tuple (

σ_{1}

,...,

σ_{n}

) such that

f

(

σ_{1}

.

..,

σ_{n}

) = 1. Hence, according to Theorem 4.9, there is a special covering for the set S

(f)

under the decomposition

d_{n}

(f)

. Let it be the set

c_{n}

S = {

F_{1}^{σ_{1}}

,...,

F_{n}^{σ_{n}}

1) If the set

c_{n} S

is an

{sM}^{α}

-covering for the set

S (f)

, then all clauses are found in the

α

-domain of the corresponding decomposition, so by the arguments of Remark 6.2, all they contain a negative literal, if

α

=0, or all they contain a positive literal, if

α

=1.

2) Assume that

c_{q_{1}}

,...,

c_{q_{l}}

are clauses of the function

f

such that for some

α_{} \in {0, 1}

{

c_{q_{1}}

,...,

c_{q_{l}}

}

=

(f)

M^{α}

Since there is a special covering for the set S

(f)

then by Theorem 4.4, {

c_{q_{1}}

,...,

c_{q_{l}}

} is a reachable set. Suppose that {(

F_{i_{1}}^{0}

F_{i_{1}}^{1}

),..., (

F_{i_{k}}^{0}

F_{i_{k}}^{1}

)} is the set of replacement steps of the decomposition

d_{n}

(f)

that ensure the

s M^{α}

-reachability of all elements {

c_{q_{1}}

,...,

c_{q_{l}}

}. After the permutation the components of all these ordered pairs we obtain the special decomposition (

i_{1}

,...,

i_{k}

)

I

(

d_{n}

(f)

)). Obviously, as a result, all clauses of the set S

(f)

will be in the

α

-domain of the resulting decomposition.

Consider the function (

i_{1}

,...,

i_{k}

)

h^{I} (x_{1}

,...,

x_{n}

) generated by the special decomposition.

(

i_{1}

,...,

i_{k}

)

I

(

d_{n}

(f)

)).

Since all clauses of this function are included in the

α

-domain of the decomposition.

(

i_{1}

,...,

i_{k}

)

I

(

d_{n}

(f)

)),

then all they contain a negative literal, if

α

= 0, or all they contain a positive literal, if

α

= 1.

This means that, the function (

i_{1}

,...,

i_{k}

)

h^{I} (x_{1}

,...,

x_{n}

) is represented in proportional conjunctive normal form. At the other hand, the function (

i_{1}

,...,

i_{k}

)

h^{I} (x_{1}

,...,

x_{n}

) is obtained by inverting the literals of the variable

x_{i_{1}}

,...,

x_{i_{k}}

in the function

f

(

x_{1}

,...,

x_{n}

Thus, if

f

(

x_{1}

,...,

x_{n}

) is a satisfiable function, then it can be transformed into a function represented in proportional conjunctive normal form using literal inversions. ∇

7. Instead of an Afterword

The importance of the result of Theorem 5.5 is that for any

α \in

{0, 1}, having a set of elements {

e_{q_{1}}

,...,

e_{q_{l}}

} not included in the

α

-domain of the given decomposition, we can search for the

{sM}^{α}

-reachability of each of these elements, considering them in any order.

The importance of the result of Theorem 6.5 is that the theorem describes one of the necessary natures of the class of satisfiable Boolean functions. That is:

The function is included in this set if and only if it can be transformed into a function in Proportional conjunctive normal form using literal inversions.

At the same time, some important questions associated with these results remain open: How to find ordered pairs that ensure the reachability of a given element, or how conclude that such ordered pairs do not exist. Also, how find the required literals for further inversion.

These questions will certainly determine the direction of research in the next article.

Abbreviations

CNF	Conjunctive Normal Form
satCNF	Satisfiability of Conjunctive Normal Form

Author Contributions

Stepan Margaryan is the sole author. The author read and approved the final manuscript.

Conflicts of Interest

The author declares no conflicts of interest.

References

[1]	Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H. The complexity of satisfiability problems: Refining Schaefer’s theorem. J. Comput. Syst. Sci. 75(4), 245–254 (2009).
[2]	Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach 2007.
[3]	Armin Biere, Marijn Heule, Hans van Maaren and Toby Walsh, Handbook of Satisfiability, IOS Press, 2008.
[4]	Cook, S. A., The complexity of theorem - proving procedures. In Conference Record of Third Annual ACM Symposium on Theory of Computing (1971), 151–158.
[5]	Yves Crama, Peter L. Hammer, Boolean Functions. Theory, Algorithms, and Applications, 2011.
[6]	Peter G´acs, Boston University and L´aszl´o Lov´asz, Yale University, Complexity of Algorithms Lecture Notes, Spring 1999.
[7]	Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simpliﬁed NP-complete graph problems. Theoretical Computer Science 1(3): 237–267, 1976. https://doi.org/10.1016/0304-3975(76)90059-1
[8]	S. A. Gizunov and V. A. Nosov, Recognition complexity for Sheffer classes, Mosc. Univ. Math. Bull. 51, no. 4, pp. 86–88, 1996. UDC 519.716.
[9]	A. Horn, On sentences which are true of direct unions of algebras. Journal of Symbolic Logic. 16(1): 14–21, 1951. https://doi.org/10.2307/2268661 JSTOR 2268661. S2CID 42534337.
[10]	Thomas Jech, Set Theory, The Third Millennium Edition, 2003.
[11]	Karp, R. M., Reducibility among combinatorial problems. In Complexity of Computer Computations (1972), R. E. Miller and J. W. Thatcher, Eds., Plenum Press, 85–103.
[12]	(L. A. Levin, “Universal problems of full search”, Probl. Inf. Transm., 9: 3 (1973), 265–266).
[13]	Stepan Margaryan, Special Coverings of Sets and Boolean Functions, American Journal of Mathematical and Computer Modeling (Volume 10, Issue 3), 84-97. https://doi.org/10.11648/j.ajmcm.20251003.11
[14]	J. Donald Monk, Mathematical Logic. Springer-Verlag, 1976.
[15]	Daniel Pierre Bovet and Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice-Hall, New York, 1993.
[16]	Charles C. Pinter, A Book of Set Theory, 2014.
[17]	E. A. Potseluevskaya, Approximation of Boolean functions to Schaefer’s classes. Journal of Mathematical Sciences, June 2012, vol 183.
[18]	Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987).
[19]	Kenneth H. Rosen, Discrete Mathematics and its Applications, seventh edition, 2012.
[20]	Thomas J. Schaefer, The complexity of Satisfiability Problems, 1978. Department of Mathematics University of California, Berkeley, California 94720.
[21]	Edward R. Scheinerman, Mathematics: A Discrete Introduction, Third Edition 2013.
[22]	Sipser Michael, Introduction to the Theory of Computation, 2012, Cengage Learning.

Cite This Article

Plain Text BibTeX RIS

APA Style

Margaryan, S. (2026). On Important Applications of Special Set Decomposition. American Journal of Mathematical and Computer Modelling, 11(1), 39-54. https://doi.org/10.11648/j.ajmcm.20261101.14

Copy | Download

ACS Style

Margaryan, S. On Important Applications of Special Set Decomposition. Am. J. Math. Comput. Model. 2026, 11(1), 39-54. doi: 10.11648/j.ajmcm.20261101.14

Copy | Download

AMA Style

Margaryan S. On Important Applications of Special Set Decomposition. Am J Math Comput Model. 2026;11(1):39-54. doi: 10.11648/j.ajmcm.20261101.14

Copy | Download

@article{10.11648/j.ajmcm.20261101.14,
  author = {Stepan Margaryan},
  title = {On Important Applications of Special Set Decomposition},
  journal = {American Journal of Mathematical and Computer Modelling},
  volume = {11},
  number = {1},
  pages = {39-54},
  doi = {10.11648/j.ajmcm.20261101.14},
  url = {https://doi.org/10.11648/j.ajmcm.20261101.14},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmcm.20261101.14},
  abstract = {This paper is devoted to the study of complexity of finding a special covering for a set, as well as to obtaining some important applications of special decomposition. We formulate the problem of existence of a special covering as a decision problem. To determine the complexity class in which this problem is located, we study the relationship between this problem and the Boolean satisfiability problem, treating them as formal languages. We prove that these problems are polynomially equivalent, which means that the problem of existence of a special covering for a set is an -complete problem. In this article we also introduce a new concept ‘Replaceable Subsets’. The properties of such subsets are used to fill in the missing elements needed to obtain a special set covering. It is proved that when searching for missing elements to fill a special covering, the order in which these elements are considered does not matter. This result is of great importance in the search for satisfiability of Boolean functions.},
 year = {2026}
}

Copy | Download

TY - JOUR
T1 - On Important Applications of Special Set Decomposition
AU - Stepan Margaryan
Y1 - 2026/02/06
PY - 2026
N1 - https://doi.org/10.11648/j.ajmcm.20261101.14
DO - 10.11648/j.ajmcm.20261101.14
T2 - American Journal of Mathematical and Computer Modelling
JF - American Journal of Mathematical and Computer Modelling
JO - American Journal of Mathematical and Computer Modelling
SP - 39
EP - 54
PB - Science Publishing Group
SN - 2578-8280
UR - https://doi.org/10.11648/j.ajmcm.20261101.14
AB - This paper is devoted to the study of complexity of finding a special covering for a set, as well as to obtaining some important applications of special decomposition. We formulate the problem of existence of a special covering as a decision problem. To determine the complexity class in which this problem is located, we study the relationship between this problem and the Boolean satisfiability problem, treating them as formal languages. We prove that these problems are polynomially equivalent, which means that the problem of existence of a special covering for a set is an -complete problem. In this article we also introduce a new concept ‘Replaceable Subsets’. The properties of such subsets are used to fill in the missing elements needed to obtain a special set covering. It is proved that when searching for missing elements to fill a special covering, the order in which these elements are considered does not matter. This result is of great importance in the search for satisfiability of Boolean functions.
VL - 11
IS - 1
ER -

Copy | Download

Author Information

Stepan Margaryan

Mkhitar Sebastatsi Educational Complex, Yerevan, Armenia

Contact Email

Download PDF

Submit an Article

Sections

Plain Text BibTeX RIS

APA Style

Margaryan, S. (2026). On Important Applications of Special Set Decomposition. American Journal of Mathematical and Computer Modelling, 11(1), 39-54. https://doi.org/10.11648/j.ajmcm.20261101.14

Copy | Download

ACS Style

Margaryan, S. On Important Applications of Special Set Decomposition. Am. J. Math. Comput. Model. 2026, 11(1), 39-54. doi: 10.11648/j.ajmcm.20261101.14

Copy | Download

AMA Style

Margaryan S. On Important Applications of Special Set Decomposition. Am J Math Comput Model. 2026;11(1):39-54. doi: 10.11648/j.ajmcm.20261101.14

Copy | Download

@article{10.11648/j.ajmcm.20261101.14,
  author = {Stepan Margaryan},
  title = {On Important Applications of Special Set Decomposition},
  journal = {American Journal of Mathematical and Computer Modelling},
  volume = {11},
  number = {1},
  pages = {39-54},
  doi = {10.11648/j.ajmcm.20261101.14},
  url = {https://doi.org/10.11648/j.ajmcm.20261101.14},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmcm.20261101.14},
  abstract = {This paper is devoted to the study of complexity of finding a special covering for a set, as well as to obtaining some important applications of special decomposition. We formulate the problem of existence of a special covering as a decision problem. To determine the complexity class in which this problem is located, we study the relationship between this problem and the Boolean satisfiability problem, treating them as formal languages. We prove that these problems are polynomially equivalent, which means that the problem of existence of a special covering for a set is an -complete problem. In this article we also introduce a new concept ‘Replaceable Subsets’. The properties of such subsets are used to fill in the missing elements needed to obtain a special set covering. It is proved that when searching for missing elements to fill a special covering, the order in which these elements are considered does not matter. This result is of great importance in the search for satisfiability of Boolean functions.},
 year = {2026}
}

Copy | Download