On complexity of decidability of constant modulo arithmetic
by
Tatyana Matveevna Kossovskaya
St.Petersburg State University
Coauthors: Nikolai Kirillovich Kossovski

The most of personal computers use arithmetic by modulo 2¹⁶ or 2³². That is why a complexity bound of decidability of constant modulo arithmetic is very important for computer science. This paper represents some computer science point of view.

A problem which has no polynomial in time algorithm deciding it under some condition we shall consider as a conditionally hard problem.

A conditional hardness of a P-SPACE-complete problem, P-SPACE-hard problem and many other analogous notions for some algorithm subclasses of P-SPACE is widely used now from [1].

Below for some class of algorithms Q notions of Q-difficultness, quasi-Q-completeness, and quasi-Q-hardness as useful in computer science extensions of these notions are suggested.

A phenomenon of the using in computer science of a conditionally hard mathematical problem to prove a conditional hardness of some problem is investigated. We use no reducibility analogous to polynomial reducibility in the following definitions.

Let P and FP be respectively classes of predicates and algorithms calculated in a polynomial time, Q_* be a class of predicates from Q. A problem is Q-difficult means that if such a problem belongs to FP then Q_* subset P.

The introduced notion means that if a problem may be decided by a polynomial in time algorithm then Q_* subset P. The last inclusion is a very difficult problem for a series of algorithm classes used instead of Q. For example a proof or disproof of the inclusion NP subset P is claimed by american mathematical institute as one of seven the most difficult mathematical problems of XXI century.

A notion of NP-difficult problem (where NP is a class of predicates calculated by a nondeterministic Turing Machine in polynomial time) is an extension of the notion of NP-hard problem. Of course we can use the notion of PH-difficult problem and prove that this notion and the previous one are equivalent [1], where PH is a union of all classes from the polynomial hierarchy.

A notion of FP-SPACE-difficult problem is an extension of the notion of quasi-P-SPACE-hard problem and is equivalent to the notion of quasi-P-SPACE-hard problem.

A notion of P-SPACE-difficult problem may serve as a formal extention of the last notions. Of course any P-SPACE-difficult problem is an NP-difficult problem because NP subset P-SPACE.

Let QBF be a problem of decidability of the set of all true closed propositional formulas in the signature &,   \/ ,   \lnot with a quantifier upon propositional variables. Let LIN-SPACE be a set of all predicates calculated in linear space.

Theorem 1. QBF in LIN-SPACE.

Note that the class LIN-SPACE is a proper subset of P-SPACE and hence a more precise upper bound for QBF than the one directly following from the P-SPACE-completeness of QBF [1] is proved in the Theorem 1.

Theorem 2. QBF is LIN-SPACE-difficult.

The notion of LIN-SPACE-difficult problem and the notion of P-SPACE-difficult problem are equivalent.

The proof is based on the fact that LIN-SPACE subset P is equivalent to P-SPACE subset P.

A problem is quasi-Q-hard means that such a problem belongs to FP if and only if Q_* subset P.

Corollary 1. QBF is a quasi-LIN-SPACE-hard problem.

Every NP-complete problem and every co-NP-complete problem is a NP-quasihard problem.

Every P-SPACE-complete problem is a quasi-P-SPACE-hard problem.

Corollary 2. QBF is a quasi-LIN-SPACE-hard problem.

We know that LIN-SPACE subset P is equivalent to P-SPACE subset P [1]. So the notion of quasi-LIN-SPACE-hard problem and the notion of quasi-PSPACE-hard problem are the same notions.

We say that a problem is quasi-Q-complete if such a problem belongs Q and it is a quasi-Q-hard problem.

Corollary 3. QBF is a quasi-LIN-SPACE-complete problem.

The notions of quasi-Q-hard problem and quasi-Q-complete problem are different ones (for example when Q=LIN-SPACE). This is because the notions of quasi-LIN-SPACE-complete problem and quasi-PSPACE-complete problem are different ones.

Corollary 4. LIN-SPACE =/= P and FLIN-SPACE =/= FP.

Here FLIN-SPACE is a class of algorithms calculated in a polynomial time.

Theorem 3. Decidability of constant modulo arithmetic is a PSPACE-complete problem.

The following theorem is a strengthening of the prvious one.

Theorem 4. Decidability of constant modulo arithmetic is a quasi- LIN-SPACE-complete problem.

Corollary 5. Decidability of constant modulo arithmetic belongs to P is equivalent to P = PSPACE and is equivalent to LIN-SPACE subset P.

These results are continuation of [2] where the next teorem was formulated. For every k, m if k >= 1 and m >= 2 then the problem of decidability of the classic predicate logic of the order k upon individual domain containing not more than m elements, not more than m-ary functions and predicates is a P-SPACE-complete problem and the decision algorithm belongs to the class LIN-SPACE and consequently to EXP-LIN-TIME.

We suppose that these investigations are useful for computer science students.

References

1. M.R.Garey, D.S.Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. San Francisco, 1979.

2. Kossovski N.K. Predicate logics of the fixed order upo the bounded domain. // Abstr. of Intern. conf. Mathematical Logic, Algebra and Set Theory dedicated to the 100-th anniversary of P.S.Novikov, 2001, p.24.

Date received: March 18, 2002