About Complexity of Constant Modulo Arithmetic
by
Nikolai Kossovski
St.Petersburg State University
Coauthors: Tatiana Kossovskaya

The most of modern personal computers use arithmetic modulo 2¹⁶ or 2³². That is why complexity bounds of decidability of constant modulo arithmetic are important for the theoretical foundation of computer science. In [1] it is proved that decidability of constant modulo arithmetic is a P-SPACE -complete problem. Some more exact results are proved below.

Now the relation between the classes P , NP and P-SPACE is of great interest. The notions of NP - and P-SPACE -compleeteness use the notion of polynomial reducibility in their definitions. But sometimes the checkig of polynomial reducibility is rather difficult. Notions introduced in [2] provide conditional hardness (not belonging to the class P ) of a problem but do not contain polynomial reducibility in their definitions.

Let Q  be a class of algorithms and Q^* - the class of all predicates from Q  such that the question of whether Q ^* subset P or not is open. Notions of Q-difficult, quasi Q-hard and quasi Q-complete problems for some class of algorithms Q  were introduced in [2] as extentions of such notions as NP-complete, NP-hard, NP-complete in the strong sense, P-SPACE -complete, P-SPACE -hard problems and some analogous notions for some classes of algorithms from P-SPACE .

Let P  and FP  be respectively classes of pedicates and algorithms computable by a deterministic Turing nachine in a polynomial time.

The problem Z is called Q -difficult if there exists an algorithm S_Z which solves the problem Z and S_Z in FP  implies Q ^* subset P.

The problem Z is called Q -hard if there exists an algorithm S_Z which solves the problem Z and S_Z in FP  is equivalent to Q ^* subset P.

The problem Z is called quasi Q -complete if there exists an algorithm S_Z which solves the problem Z and, the first, S_Z in Q  and, the second, S_Z in FP  is equivalent to Q ^* subset P.

It is evident that a NP-complete and a NP-hard problems are NP-difficult. If P subset NP  then classes of quasi NP-hard and quasi NP-comlete problems are respectively the complementation to FP and NP \ P  and the classes of NP-difficult and quasi NP-hard problems coincide.

If P = NP  then every problem is NP-difficult and classes of quasi NP-hard and quasi NP-comlete problems are equal to the class FP. The same is valid with the substitution P-SPACE instead of NP.

The introduced notions permit to define (with Q = LIN-SPACE ) such notions as quasi LIN-SPACE-hard and quasi LIN-SPACE-complete problems. The notions of LIN-SPACE-difficult and P-SPACE-difficult occur to be equivalets because LIN-SPACE subset P  iff P-SPACE subset P  [3].

A formal elementary theory in a signature with a support {-N+1, ... ,   0,   1,   2, ... , N} (numbers are written in a positional notation), functions of addition and multiplication modulo 2N and a predicate <= will be called a constant modulo arithmetic. It should be noted that subtraction, division with a remainder and the equality predicate are definable in such a theory.

The problem of decidability of constant modulo arithmetic will be denoted by DCMA.

Lemma 1.DCMA in LIN-SPACE.

Lemma 2 (from [1]). DCMA   is a P-SPACE-complete problem.

Lemma 3.DCMA  is a LIN-SPACE-difficult problem .

The next theorem is an immediate consequence from lemmas 1 and 3.

Theorem 1. DCMA   is a quasi LIN-SPACE -complete problem .

The union of all classes of a polynomial hierarhy [3, 4] will be denoted by PH. The next theorems clarify justification of the introduction of the notions of quasi LIN-SPACE-hardness and quasi LIN-SPACE-completeness and show that the class LIN-SPACE   differs from the classes P, PH   and P-SPACE   usually used to prove completeness or hardness of some problem.

Theorem 2. LIN-SPACE =/= P.

Theorem 3 (from [3]). LIN-SPACE subset P  if and only if P = P-SPACE.

Corollary. If LIN-SPACE subset P  then P = NP.

Theorem 4. LIN-SPACE subset PH  if and only if PH = P-SPACE.

Theorem 5. LIN-SPACE =/= PH.

The proof of this theorem is based on the following lemmas.

Lemma 4. P(PH) = PH.

Lemma 5. P(LIN-SPACE) = P-SPACE.

Corollary of Theorem 2. FLIN-SPACE =/= FP.

The main idea of this communication was presented at the XIII International school-seminar "Synthesis and completeness of control systems", Penza, Russia, October 2002 [2].

References

1. Kossovski N.K. Predicate logics of the fixed order upon the bounded domain. // Abstr. International conference Mathematical Logic, Algebra and Set Theory dedicated to the 100-th anniversary of P.S.Novikov. Moscow 2001. P.24.

2. Kossovski N.K., Kossovskaya T.M. Quasi LIN-SPACE completness of constant modulo arithmetic. // Proc. XIII International school-seminar "Synthesis and completeness of control systems", Moscow, Moscow State University, 2002. PP. 122-128. (In Russin.)

3. Garey M.R., Johnson D.S. Computers and Intractability. A Guide to the Theory of NP-Completeness. - Bell Laboratories, Murray Hill, New Jersey. W.H.Freeman and Co., Son-Francisco, 1979.

4. Du D. Ko K. Theory of computational complexity. - New York. JOHN WILEY & SONS INC, 2000. 491p.

Date received: May 24, 2003