\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={Some NP-Hard Problems for the Simultaneous Coprimeness of Values of Linear Polynomials},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2017-01-15 (revised: 15 January 2017)}
\def\TheID{\makeatother }
\def\TheDate{2017-01-15}
\title{Some NP-Hard Problems for the Simultaneous Coprimeness of Values of Linear Polynomials}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{Starchak  M.R}

             \author[2]{Kosovskii  N.K.}

             \author[3]{Kosovskaya  T.M.}

             \affil[1]{  St. Petersburg State University}

\renewcommand\Authands{ and }

\date{\small \em Received: 11 December 2016 Accepted: 2 January 2017 Published: 15 January 2017}

\maketitle


\begin{abstract}
        


The algorithmic-time complexity of some problems connected with linear polynomials and coprimeness relation on natural numbers is under consideration in the paper.We regard two easily stated problems. The first one is on the consistency in natural numbers from the interval of a linear coprimeness system. This problem is proved to be NP-complete. The second one is on the consistency in natural numbers of a linear coprimeness and discoprimeness system for polynomials with not greater than one non-zero coefficient. This problem is proved to be NP-hard.Then the complexity of some existential theories of natural numbers with coprimeness is considered. These theories are in some sense intermediate between the existential Presburger arithmetic and the existential Presburger arithmetic with divisibility.

\end{abstract}


\keywords{NP, NP-completeness, NP-hardness, coprimeness of values of linear polynomials, simultaneous divisibility of linear polynomials, existential theories w}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 
\section[{I. Introduction}]{I. Introduction}\par
he proof of NP-hardness of a certain computational problem gives us rather strong assurance of the absence of any polynomial-time algorithm for this problem. Hence, the existence of such proof gives us not only theoretical but also an important practical result for a working programmer. On the other hand, number-theoretical relations like divisibility or coprimeness of integers provides us one of the most natural languages for stating computational problems. We thus come to the study of the algorithmic-time complexity of the decision problems for various subclasses of arithmetic which are sometimes referred as weak arithmetics (see \hyperref[b17]{[16]}). These reasons motivate the appearance of this paper.\par
The problem of integer linear programming (ILP) is well-known and one of the first to be proved NPcomplete (see, \hyperref[b1]{[2]} and \hyperref[b5]{[6]}, problem MP1). It can be regarded as a problem of consistency in non-negative integers of a system of linear equations with integer coefficients. In the sense of the weak arithmetics complexity this result can be interpreted as the NP-T completeness of the decision problem for the existential Presburger Arithmetic ?Th??;+,=,0,1? (abbreviated as ?PA). The decidability of Presburger Arithmetic is a classical result \hyperref[b16]{[15]} and the complexity of its subclasses is studied rather extensively. For example, the paper \hyperref[b6]{[7]} completes the classification of the time-complexity results corresponding fixed number of quantifier alternations and fixed maximum number of variables in each quantifier group. The lowest level of this subproblem hierarchy is just the famous H.W.Lenstra Jr. theorem \hyperref[b14]{[13]} on the polynomial algorithm for ILP with a fixed number of variables. As was shown in \hyperref[b4]{[5]} this result provides us with polynomial algorithms for various practical graph problems when we fix the value of some natural parameter of a given graph. In other words, there was proved the fixed-parameter tractability of these problems by rewriting each one as an instance of ILP. In this paper, we will prove NP-hardness of some problems from the extensions of ?PA.\par
The time-complexity of ?PA extended with thedivisibility relation | ( ) x y z y x z â??" ? = ?\par
was studied in \hyperref[b13]{[12,}\hyperref[b15]{14]}. For this problem we will use the abbreviation ?PAD. In non-deterministic polynomial time the problem is reducible to the consistency in non-negative integers of a system of linear divisibilities of the form,0 ,\textbf{1 1 , ,0 ,1 1 , 1 ( ...}| ... ). m i i i n n i i i n n i a a x a x b b x b x = + + + + + + ?\textbf{(1)}\par
L.Lipshitz in \hyperref[b15]{[14]} proved that this problem is NPcomplete for every fixed number of divisibilities m?5, whereas the general problem, as was shown in \hyperref[b13]{[12]} by A.Lechner, J.Ouaknine and J.Worrell, is in NEXPTIME.\par
The exact complexity of ?PAD remains an open problem, and the answer is of considerable interest as it will effect on the related problems of formal verification (see, for example, \hyperref[b2]{[3,}\hyperref[b12]{11]}). Some NP-complete problems with an arbitrary number of divisibilities but with restrictions on the values of the coefficients of linear polynomials are presented in \hyperref[b10]{[10]}.\par
One of the possible approaches to solve this problem is to establish complexity of some intermediate theories, that is, simultaneously extensions of ?PA and subclasses of ?PAD. This question has not been studied apparently because of the common belief that ?PAD is in NP citing the paper \hyperref[b15]{[14]}. This inaccuracy was firstly pointed at by the authors of \hyperref[b13]{[12]}. For example, the paper \hyperref[b3]{[4]}  The object of consideration of this paper is the complexity of linear systems with coprimeness relation of the form,0 ,\textbf{1 1 , ,0 ,1 1 , 1 (}\par
... ... ).m i i i n n i i i n n i a a x a x b b x b x = + + + ? + + + ?\textbf{(2)}\par
We will further prove NP-hardness of a system of linear coprimeness and discoprimeness for linear polynomials with not greater than one non-zero coefficient in each polynomial. Formally, this system has form1 2 1 1 ( ) ( ) ( ( ) ( )), m m i i j j i j f x g x f x g x = = ? ? ¬ ? ? ?\textbf{(3)}\par
where ??=( )and each linear polynomial (??), (??) has the form for some[1, ]. j n ?\par
From this result we can derive NP-hardness of the decision problem for the existential theory of natural numbers for with coprimeness relation ?Th??;S,??.\par
Note that all thus defined problems on simultaneous coprimeness of values of linear polynomials can be rewritten in a form of a system of divisibilities of values of linear polynomials. One has to introduce new variables to use the following formulas:( | |1 ) ( ) (2 | 2 | ). x y u x u y u x y v v x v y ? â??" ? ? + ¬ ? â??" ? + ? +\textbf{(4)}\par
II. Two NP-Hard Problems for the Simultaneous Coprimeness of Values of Linear Polynomials\par
By natural numbers we will further assume nonnegative integers ?= \{0, 1, 2 ?\}. As it was defined in the introduction, the relation x y\par
? on natural numbers is true iff the greatest common divisor of x and y equals , thus we have (0 0) ¬ ? and that for every x ? the formula 1 x ? is true. We can now define a series of problems, depending on the parameter . k ? 
\section[{Simultaneous Coprimeness of values of Linear Polynomials in the interval [k, k+1] (?LP[k, k+1]). INPUT: A set of m pairs of (n+1)-dimensional vectors (( ),(}]{Simultaneous Coprimeness of values of Linear Polynomials in the interval [k, k+1] (?LP[k, k+1]). INPUT: A set of m pairs of (n+1)-dimensional vectors (( ),(}\par
))with natural entries for[1, ]. i m ? QUESTION: Is the linear system ,0 ,\textbf{1 1 , ,0 ,1 1 , 1 (}\par
... ... )m i i i n n i i i n n i a a x a x b b x b x = + + + ? + + + ? consistent in natural numbers from the interval [k, k+1]? Let ?03LP[k, k+1] be a subproblem of ?LP[k, k+1]\par
in which each pair of coprime linear polynomials contains one with exactly three non-zero coefficients and the other is a natural number.Theorem 1. For every k ? the problem ?03LP[k, k+1] is NP-complete.\par
Proof. That the problem is in the class NP is obvious because every variable takes it values from the given interval of natural numbers.\par
To prove NP-hardness of ?03LP[k, k+1] we will construct a polynomial reduction of ONE-IN-THREE 3SAT from \hyperref[b5]{[6]} to our problem. The truth of exactly one literal in every clause can be expressed via expression,1\textbf{,2 ,3 3 (3 2)}\par
.i i i k k x x x + ? + +\textbf{(5)}\par
Logical constants true and false are encoded respectively by numbers k+1 and k. Every negated literal ¬x is substituted in the corresponding expression by a new variable x' and we add to the system three new expressions3 (3 2) ' 3 (3 2) ' 3 (3 2) , k k x x u k k x x v k k u v w + ? + + + ? + + + ? + + (6) ?? 1 , ? , ?? ?? ð??"ð??" ?? ð??"ð??" ?? ?? ??=??+1\par
a ??,0 +a ???? ?? ?? the successor functiona i,O, a i, 1, ? , a i,n ?? i,0 , ?? i,1 ,?, ?? i,n\par
of ?PAD has the following sentences: "In \hyperref[b4]{[5]} the algorithm of \hyperref[b3]{[4]} is made into decision procedure of class NP: hence each subdivisibility set is in the class NP. 
\section[{[?]}]{[?]}\par
Here we focus on other structural properties of these sets [?]". In \hyperref[b7]{[8,}\hyperref[b8]{9]} it was proved NP-completeness for some kinds of systems of linear congruences ?, incongruences ? and dis-equations ?, supplemented in some cases with geometric interpretations.\par
Here we use the notationGCD( , ) 1, x y x y ? â??" = where GCD( , )\par
x y is the greatest common divisor of nonnegative integers and , assuming(0 0). ¬ ?\par
The problem of consistency of the linear system (2) will be denoted as SIMULTANEOUS COPRIMENESS OF LINEAR POLYNOMIALS (?LP). We will state the NPcompleteness of a series of ?LP problems with the values of the variables taken from an interval of nonnegative integers. The relation 
\section[{[ , ]}]{[ , ]}\par
x a b ? is existentially definable using equality predicate. As a corollary, we get NP-hardness of the decision problems for existential theories of natural numbers with addition, equality and coprimeness relation and also its restriction to the theory without equality. It is not known whether the equality predicate is definable even in universal theory. It was only proved in \hyperref[b18]{[17]} (see also the survey \hyperref[b17]{[16]}) that the definability of equality within arithmetic with addition and coprimeness is equivalent to the truth of the number-theoretic Erdös-Woods conjecture.\par
x y 
\section[{= x y}]{= x y}\par
We therefore can conclude that each NP-hard problem mentioned above is in NEXPTIME complexity class. The simple definition of coprimeness in terms of divisibilities suggests that ?Th??;S,?? can be proved to be in the class NP using the complexity analysis of the ?PAD decision problem from \hyperref[b13]{[12]}. This possibility is discussed in some concluding remarks after the ?Th??;S,?? NPhardness proof.   i i i i i u b u x b a ¬ ? ? ? + ?\par
Thus, for every SI instance we have constructed the instance of ?\&Dis?LP of the form1 1 ( ( )) ( ). m m i i i i i i i u x b a u b = = ? + ? ? ¬ ? ? ?\textbf{(7)}\par
As this construction takes not greater than polynomial number of steps of a Turing machine, the problem ?\&Dis?LP is NP-hard. Corollary 1 from the Theorem 2. The problem ?\&Dis?LP is NP-hard.\par
Note that in fact we have proved a stronger theorem as every coefficient in the constructed system (7) equals to one. This provides us with one subclass of ?Th??;S,?? formulas with NP-hard decision problem. We will state some corollaries from these two theorems, concerning complexity of decision problems for existential theories in the following section. 
\section[{III. Some Corollaries on the Time-Complexity of the Decision Problems for Existential Theories with Coprimeness Relation}]{III. Some Corollaries on the Time-Complexity of the Decision Problems for Existential Theories with Coprimeness Relation}\par
The problems ?LP[k, k+1] and ?\&Dis?LP can be interpreted as problems of validity in natural numbers for some classes of existentially closed formulas of the first-order language for coprimeness with addition or with successor function. We should only take care of the length of each formula that corresponds to an instance of ?LP[k, k+1] or ?\&Dis?LP. Let us first prove some lemmas on the definability of certain predicates in the theories with coprimeness. Lemma 1. The relations =0 and =1 on natural numbers are existentially definable by successor and the coprimeness relation. x y ?\par
Proof. These definitions are: 1 x x x = â??" ? and 0 1 1 . x x x = â??" + ? + Lemma 2.n a = ? ? ? ? As the relation x 0 =1 is definable, we can define x 1 =2, x 2 =4, x 3 =8? x n =2 n by the formulas a i,O, a i, 1, ? , a i,n ?? i,0 , ?? i,1 ,?, ?? i,n \{(( ),( ))\}for a i,O, a i, 1, ? , a i,n ?? i,0 , ?? i,1 ,?, ?? i,n a ?? ?? ?? ?? ?? ?? ?? ??=??+1 a a\par
Proof. To prove the NP-hardness of the problem, we will construct a polynomial reduction of a special case of SIMULTANEOUS INCONGRUENCES problem which is named "anti-Chinese remainder theorem" in \hyperref[b0]{[1]}. It could be seen from the NP-completeness proof in \hyperref[b0]{[1]}, that every modulus in a system is square-free and its value is bounded polynomially in the number of the incongruences. This follows from the fact that in the polynomial reduction from 3SAT to SI, there were generated first n primes for every propositional variable from the instance of 3SAT and every modulus of the corresponding SI instance did not exceed p n p n-1 p n-2 . Thus the proof from \hyperref[b0]{[1]} implicitly gives us the NPcompleteness of the following problem. \par
.n i i i k x x k = ? ? ? + ? The predicate x y\par
? is definable by the formula with equality: ( ). u x u y ? + = From Lemma 2 it follows that every linear term ( ) i f x and ( ) i g x can be defined by a formula of polynomial size on the length of the binary representation of the integer coefficients. Thus, introducing n new variables we construct in polynomial time a formula from ?Th??;+,=,?? which is true iff the given instance ?LP[k, k+1] is solvable.\par
We thus have a series of NP-complete subproblems of the decision problem of ?Th??;+,=,?? and NP-hardness of the general decision problem of this theory.\par
Corollary 3 from the Theorem 1. The problem ?LP is NPhard. Proof. Consider the formulas from the proof of Theorem 1 in the case of k=0. The system has form:,1 ,2 ,3 1 0 m i i i i x x x = ? + + ?\textbf{(8)}\par
proved by restriction to the NP-complete problem of the consistency in natural numbers of a system of the form \hyperref[b7]{(8)}.\par
As the relation =0 is definable by Lemma 1 in the theory ?Th??;+,??, and the coefficients of linear polynomials from \hyperref[b7]{(8)} all equal one, we immediately get the following corollary. Corollary 4 from the Theorem 1. The decision problem of the theory ?Th??;+,?? is NP-hard.\par
Corollary 2 from the Theorem 2. The decision problem of the theory ?Th??;S,?? is NP-hard. Proof. To prove NP-hardness we can continue the polynomial reduction presented in the proof of Theorem 2. The relation =1 is definable in the considered theory, and therefore the unary relation ¬( ? ) is also definable for every positive integer a. As every natural number from the formula ( \hyperref[formula_18]{7}) is represented in unary, each polynomial a+x can be rewritten in the form ? ... . a times SS S x By taking existential closure of every formula of the form \hyperref[b6]{(7)} we define some formula from ?Th??;S,??. This concludes the polynomial reduction of SI to the decision problem of ?Th??; S,??.\par
A natural question is whether the decision problems considered above are in fact NP-complete. As every formula of these theories can be rewritten as a ?PAD formula, one can go through the complexity analysis of the ?PAD decision procedure from \hyperref[b13]{[12]} for some restricted class of formulas. In conclusion, we will give some remarks corresponding NP membership of the decision problem for ?Th??;S,?? formulas. 
\section[{IV. Conclusion}]{IV. Conclusion}\par
Two easily formulated number-theoretic problems for coprimeness relation on natural numbers were defined in the first section. The problem of consistency of a coprimeness system of the form (2) was shown NP-complete on every interval [k, k+1] of natural numbers. The related problem of consistency in natural numbers of a coprimeness and discoprimeness system of the form (3) was proved NP-hard when the linear polynomials have not greater than one non-zero coefficient.\par
We then derive some corollaries from these two theorems. There was established NP-hardness of the existential theories of natural numbers for coprimeness with addition ?Th??;+,?? and for coprimeness with successor function ?Th??;S,??. These problems naturally arise in such fields of computer science as formal verification or cryptography. As it is not known whether the relation of equality is definable by addition and coprimeness, we have to independently consider the theory without equality. Let us define the problem ?LP as the problem of consistency in natural numbers of a system of coprime values of linear polynomials. That is, unlike ?LP[k, k+1], this problem does not have any restriction on the values of the variables. As the formulation of ?LP is very similar to the one of ?LP[k, k+1], we do not give it explicitly. The pairs of coprime polynomials in the proof given below will provide us with the NP-hardness proof for the decision problem of the corresponding theory without equality.\par
For every natural number, we have 0 1, x x ? â??" = therefore the restriction on the variables [0,1] i x ? is necessary satisfied. NP-hardness of ?LP is Note that we use in this corollary that the problem ?LP remains NP-complete even in the case of the unary representation of the coefficients of polynomials in a system from its instance. Let us now consider formulas of the theory ?Th??;S,?? with the successor function in place of addition. The formula \hyperref[b6]{(7)} provides us with the following It could be an interesting problem i to determine whether if ?Th??;S,?? is in NP and the same question in Year 2017      \begin{figure}[htbp]
\noindent\textbf{} \par 
\begin{longtable}{P{0.85\textwidth}}
Year 2017\\
22\\
)\\
( H\\
which considers existentially definable subsets\end{longtable} \par
 
\caption{\label{tab_0}}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{} \par 
\begin{longtable}{P{0.6004211793020456\textwidth}P{0.001022864019253911\textwidth}P{0.037845968712394706\textwidth}P{0.001022864019253911\textwidth}P{0.002045728038507822\textwidth}P{0.001022864019253911\textwidth}P{0.002045728038507822\textwidth}P{0.001022864019253911\textwidth}P{0.001022864019253911\textwidth}P{0.01022864019253911\textwidth}P{0.01022864019253911\textwidth}P{0.007160048134777376\textwidth}P{0.01022864019253911\textwidth}P{0.03375451263537906\textwidth}P{0.015342960288808664\textwidth}P{0.03170878459687124\textwidth}P{0.024548736462093865\textwidth}P{0.023525872442839952\textwidth}P{0.015342960288808664\textwidth}P{0.008182912154031288\textwidth}P{0.01125150421179302\textwidth}P{0.001022864019253911\textwidth}}
\multicolumn{16}{l}{Simultaneous Coprimeness and Discoprimeness of}\\
\multicolumn{16}{l}{values of Linear Polynomials(?\& Dis?LP) INPUT: Two sets of (m 1 + m 2 ) pairs of (n+1)-dimensional vectors: 1 [1, ] i m ?}\tabcellsep Year 2017\\
\multicolumn{2}{l}{and \{((}\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \multicolumn{2}{l}{),(}\tabcellsep \tabcellsep ))\}for\tabcellsep j\tabcellsep 2 [1, ] m ?\tabcellsep with\\
\multicolumn{11}{l}{natural entries.}\tabcellsep \tabcellsep \tabcellsep \tabcellsep \\
\multicolumn{15}{l}{QUESTION: Is the system}\\
1 m\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \\
1 = ? i\tabcellsep (\tabcellsep \multicolumn{2}{l}{i a}\tabcellsep \multicolumn{3}{l}{,0}\tabcellsep \multicolumn{2}{l}{+}\tabcellsep \multicolumn{2}{l}{,1 1 a x i}\tabcellsep \multicolumn{2}{l}{... + +}\tabcellsep \multicolumn{3}{l}{, i n n a x b b x ,0 ,1 1 i i ? +}\tabcellsep ... + +\tabcellsep , i n n b x\tabcellsep )\tabcellsep ?\\
2 m\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \\
\multicolumn{3}{l}{1 = ¬ ( ? j}\tabcellsep \multicolumn{2}{l}{a}\tabcellsep j\tabcellsep \multicolumn{2}{l}{,0}\tabcellsep \multicolumn{2}{l}{+}\tabcellsep \multicolumn{2}{l}{,1 1 a x j}\tabcellsep \multicolumn{2}{l}{... + +}\tabcellsep , j n n a x b ?\tabcellsep j\tabcellsep ,0\tabcellsep +\tabcellsep ,1 1 b x j\tabcellsep ... + +\tabcellsep , j n n b x\tabcellsep )\\
\multicolumn{15}{l}{consistent in natural numbers?}\\
\tabcellsep \tabcellsep \multicolumn{14}{l}{Let ?\&Dis?11LP be a subproblem of}\\
\multicolumn{16}{l}{?\&Dis?LP such that each linear polynomial has not}\\
\multicolumn{16}{l}{greater than one non-zero coefficient and every}\\
\multicolumn{16}{l}{coefficient and constant term is represented in unary. Theorem 2. The problem ?\&Dis?11LP is NP-hard.}\tabcellsep ( ) H\\
\multicolumn{16}{l}{Simultaneous Incongruences (SI ) (Implicit in [1, Theorem}\\
5.5.7]\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \\
\multicolumn{15}{l}{INPUT: A set of ordered pairs (}\tabcellsep ) of positive integers,\\
\multicolumn{15}{l}{represented in unary, with}\end{longtable} \par
 
\caption{\label{tab_1}}\end{figure}
 			\footnote{© 2017 Global Journals Inc. (US)} 			\footnote{© 20 7 Global Journa ls Inc. (US)} 		 		\backmatter  			 \par
a times SS S x written on the tape of a Turing machine as the string a+x for the integer a represented in binary. Introducing new variables u i and v i while rewriting every coprimeness formula in the form of divisibility formula using the formulas (4), we get a ?PAD instance of rather convenient for the subsequent complexity analysis form. Every linear polynomial has form a+x, and the formula is already increasing (in the sense of \hyperref[b13]{[12]}) with respect to the total ordering\par
variables. An attempt to apply the ?PAD decision procedure from \hyperref[b13]{[12]} on such restricted class of divisibility formulas to get an NP upper bound could be the subject of the subsequent research.\par
This page is intentionally left blank 			 			  				\begin{bibitemlist}{1}
\bibitem[ Mathematics. Mechanics. Astronomy ()]{b9}\label{b9} 	 		\textit{},  	 	 		\textit{Mathematics. Mechanics. Astronomy}  		2016. 49  (3)  p. .  	 
\bibitem[ Astronomy ()]{b11}\label{b11} 	 		\textit{},  	 	 		\textit{Astronomy}  		2017. 4  (62)  p. .  	 
\bibitem[Bach and Shallit ()]{b0}\label{b0} 	 		\textit{Algorithmic number theory, I: Efficient algorithms},  		 			E Bach 		,  		 			J Shallit 		.  		1996. Cambridge, MA: MIT Press.  	 
\bibitem[Borosh and Treybig ()]{b1}\label{b1} 	 		‘Bounds on positive integral solutions of linear diophantine equations’.  		 			I Borosh 		,  		 			L B Treybig 		.  	 	 		\textit{Proceedings of the American Mathematical Society}  		1976. 55  (2)  p. .  	 
\bibitem[Garey and Johnson ()]{b5}\label{b5} 	 		\textit{Computers and Intractability: A guide to the theory of NPcompleteness},  		 			M R Garey 		,  		 			D S Johnson 		.  		1979. New York: W. H. Freeman and co.  	 
\bibitem[Fellows et al. ()]{b4}\label{b4} 	 		‘Graph layout problems parameterized by vertex cover’.  		 			M R Fellows 		,  		 			D Lokshtanov 		,  		 			N Misra 		,  		 			F A Rosamond 		,  		 			S Saurabh 		.  	 	 		\textit{Proceedings of the 19th International Symposium on Algorithms and Computation},  				 (the 19th International Symposium on Algorithms and Computation)  		2008. p. .  	 
\bibitem[Lenstra ()]{b14}\label{b14} 	 		‘Integer programming with a fixed number of variables’.  		 			H W J Lenstra 		.  	 	 		\textit{Mathematics of Operations Research}  		1983. 8  (4)  p. .  	 
\bibitem[Kosovskii et al.]{b10}\label{b10} 	 		‘NP-complete problems for systems of divisibilities of values of linear polynomials’.  		 			N K Kosovskii 		,  		 			T M Kosovskaya 		,  		 			N N Kosovskii 		,  		 			M R Starchak 		.  	 	 		Vestnik SPbSU. Mathematics. Mechanics  		 	 
\bibitem[Kosovskii et al.]{b8}\label{b8} 	 		\textit{NP-completeness conditions for verifying the consistency of several kinds of systems of linear diophantine dis-equations},  		 			N K Kosovskii 		,  		 			T M Kosovskaya 		,  		 			N N Kosovskii 		.  		Vestnik SPbSU.  	 
\bibitem[Kosovskii et al. ()]{b7}\label{b7} 	 		‘NP-completeness conditions for verifying the consistency of several kinds of systems of linear diophantine discongruences’.  		 			N K Kosovskii 		,  		 			T M Kosovskaya 		,  		 			N N Kosovskii 		.  	 	 		Vestnik SPbSU. Mathematics. Mechanics. Astronomy  		2016. 49  (1)  p. .  	 
\bibitem[Bundala and Ouaknine ()]{b2}\label{b2} 	 		‘On parametric timed automata and one-counter machines’.  		 			D Bundala 		,  		 			J Ouaknine 		.  	 	 		\textit{Information and Computation}  		2017. 253 p. .  	 
\bibitem[Lechner et al. ()]{b13}\label{b13} 	 		‘On the complexity of linear arithmetic with divisibility’.  		 			A Lechner 		,  		 			J Ouaknine 		,  		 			J Worrell 		.  	 	 		\textit{Proceedings of 30th Annual IEEE Symposium on Logic in Computer Science},  				 (30th Annual IEEE Symposium on Logic in Computer Science)  		2015. p. .  	 
\bibitem[Woods ()]{b18}\label{b18} 	 		\textit{Some problems in logic and number theory, and their connections},  		 			A Woods 		.  		1981.  		 			University of Manchester 		 	 	 (PhD Thesis) 	 (the case of every term from this theory of the form ? ..) 
\bibitem[Lipshitz ()]{b15}\label{b15} 	 		‘Some remarks on the diophantine problem for addition and divisibility’.  		 			L Lipshitz 		.  	 	 		\textit{Bulletin de la Société mathématique de Belgique. Série B}  		1981. 33  (1)  p. .  	 
\bibitem[Haase ()]{b6}\label{b6} 	 		‘Subclasses of Presburger arithmetic and the weak EXP hierarchy’.  		 			C Haase 		.  	 	 		\textit{Proceedings of the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic and the 29th Annual IEEE Symposium on Logic in Computer Science},  				 (the Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic and the 29th Annual IEEE Symposium on Logic in Computer Science)  		2014. p. .  	 
\bibitem[Lechner ()]{b12}\label{b12} 	 		‘Synthesis problems for one-counter automata’.  		 			A Lechner 		.  	 	 		\textit{Proceedings of 9th International Workshop on Reachability Problems},  				 (9th International Workshop on Reachability Problems)  		2015. p. .  	 
\bibitem[Van Den Dries and Wilkie ()]{b3}\label{b3} 	 		‘The laws of integer divisibility, and solution sets of linear divisibility conditions’.  		 			L Van Den Dries 		,  		 			A J Wilkie 		.  	 	 		\textit{Journal of Symbolic Logic}  		2003. 68  (2)  p. .  	 
\bibitem[Richard ()]{b17}\label{b17} 	 		‘What are weak arithmetics?’.  		 			D Richard 		.  	 	 		\textit{Theoretical Computer Science},  				2001. 257 p. .  	 
\bibitem[Presburger ()]{b16}\label{b16} 	 		‘Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt’.  		 			M Presburger 		.  	 	 		\textit{Comptes rendus du 1er Congrès des Mathématiciens des Pays Slaves},  				1929. p. .  	 
\end{bibitemlist}
 			 		 	 
\end{document}
