---
author:
- 'SergeyV.Yakhontov'
title: ' [[**P**]{}]{}$\,=\,$[[**NP**]{}]{}'
---

[ ]{}

computational complexity, Turing machine, class [[**P**]{}]{}, class [[**NP**]{}]{}, [[**P**]{}]{} vs. [[**NP**]{}]{} Problem, class [[**FP**]{}]{}, accepting computation paths, tape-consistent path existence problem, program analysis, linear programming.

Introduction
============

This paper concerns the complexity classes of languages over finite alphabets (wherein the number of symbols is equal to or more than two) that are decidable by Turing machines.

It follows from the definition of classes [[**P**]{}]{} and [[**NP**]{}]{} [@DK00] that [[**P**]{}]{}$\,\subseteq\,$[[**NP**]{}]{} wherein [[**P**]{}]{} is the shortened indication of [[**PTIME**]{}]{} and [[**NP**]{}]{} is the shortened indication of [[**NPTIME**]{}]{}. However, the problem of the strictness of the inclusion, referred to as [**the [[**P**]{}]{} versus [[**NP**]{}]{} Problem**]{}, is one of the most important unsolved problems in the theory of computational complexity.

The [[**P**]{}]{} vs. [[**NP**]{}]{} Problem was introduced by Stephen Cook in 1971 [@Cook71] and independently by Leonid Levin in 1973 [@lL73]. A detailed description of the problem in [@ClayCook] formulates it as follows: Can each language over a finite alphabet, which is decidable by [**a polynomial time non-deterministic single-tape Turing machine**]{}, also be decided by [**a polynomial time deterministic single-tape Turing machine**]{}? The shortened formulation of the problem is [[**P**]{}]{}$\,=$$?\,$[[**NP**]{}]{}.

The papers [@S92; @C03; @W07; @F09; @L10] contain detailed surveys on the [[**P**]{}]{} vs. [[**NP**]{}]{} Problem.

The present paper proves that [[**P**]{}]{}$\,=\,$[[**NP**]{}]{}. The proof, suggested in this paper, is a constructive one: The program of a polynomial time deterministic multi-tape Turing machine $M\langle\exists AcceptingPath\rangle$, which determines if there exists an accepting computation path of a polynomial time non-deterministic single-tape Turing machine $M\langle NP\rangle$ (more precisely, an accepting computation path of the computation tree of machine $M\langle NP\rangle$ on the input), is constructed (machine $M\langle \exists AcceptingPath\rangle$ is different for each machine $M\langle NP\rangle$).

It is known that problem [[**3-CNF-SAT**]{}]{} is [[**NP**]{}]{}-complete [@Cook71; @lL73] (Cook–Levin theorem); this theorem is usually used as a basis to solve the [[**P**]{}]{} vs. [[**NP**]{}]{} Problem.

Most of the works on the attempts to solve the [[**P**]{}]{} vs. [[**NP**]{}]{} Problem can be found on the Internet at [@ArxivOrgCC] and [@PvsNPPage]. It seems most of these works use reductions $$L\le_{m}^{P}{\text{\bf 3-CNF-SAT}}\le_{m}^{P}\ldots\le_{m}^{P}L'$$ wherein language $L\in\,$[[**NP**]{}]{} and $\le_{m}^{P}$ is polynomial time many-one reduction; a detailed list of these reductions can be found in [@GJ79]. In particular, reductions to [[**ILP**]{}]{} (Integer Linear Programming) are often used: $$L\le_{m}^{P}{\text{\bf 3-CNF-SAT}}\le_{m}^{P}\ldots\le_{m}^{P}{\text{\bf ILP}};$$ a detailed list of reductions to [[**ILP**]{}]{} can be found in [@S03].

Regarding the works at [@ArxivOrgCC; @PvsNPPage], the author of the present paper could not find any work that contains a concept similar to the concept suggested in the present paper.

The solution suggested in the present paper is completely different from the well-known approaches to solve the problem; namely, reduction $L\le_{m}^{P}{\text{\bf 3-CNF-SAT}}$ is not used in the present paper. The concept of the construction of machine $M\langle\exists AcceptingPath\rangle$ suggested in this paper is based on the following general idea:

1.  [define the set of the tape-arbitrary paths in the acyclic control flow graph of polynomial size of a deterministic computer program such that this set is the disjoint union of the set of the tape-consistent paths and the set of the tape-inconsistent paths; ]{}

2.  [using reduction to problem [[**LP**]{}]{}, determine if there exists a tape-consistent path in the control flow graph; the reduction is based on the results of reaching definitions analysis for the deterministic computer program;]{}

3.  [there is one-to-one mapping from the tape-consistent accepting paths to the accepting computation paths of machine $M\langle NP\rangle$, so one can determine if there exists an accepting computation path of machine $M\langle NP\rangle$.]{}

In contrast to problem [[**ILP**]{}]{}, a fractional solution of problem [[**LP**]{}]{} can be found in polynomial time [@Kh80; @K84].

The main feature of the tape-arbitrary paths is that the computations on a path of such kind starting at a point do not depend on the computations from the start of the path to this point. This fact is the main reason why exponential time computations are represented by a graph of polynomial size in the present paper.

Machine $M\langle\exists AcceptingPath\rangle$ computes also a $t(n)_{\le}$-length accepting computation path of machine $M\langle NP\rangle$ in polynomial time in $t(n)$, wherein $t(n)$ is an upper bound of the time complexity of machine $M\langle NP\rangle$.

Machine $M\langle\exists AcceptingPath\rangle$ works in polynomial time in $t(n)$ because the space used to compute the computation steps of a tape-arbitrary sequence of the computation steps of machine $M\langle NP\rangle$ is logarithmic in $t(n)$ only.

Preliminaries
=============

In the present paper

1.  [$t(n)$ is an upper bound of the time complexity of machine $M\langle NP\rangle$,]{}

2.  [‘a path in graph’ means a simple path in graph,]{}

3.  [in the estimations of the time complexity of the algorithms, ‘TM steps’ and ‘TM tape cells’ mean steps and tape cells accordingly on Turing machine,]{}

4.  [in the estimations of the time complexity of the algorithms, ‘VN operations’ and ‘VN memory cells’ mean operations and memory cells accordingly on a computer with Von Neumann architecture, and]{}

5.  [all the propositions whose proofs are obvious or follow from the previous text are omitted.]{}

This section contains general information that is used in all the constructions in the present paper.

Non-deterministic computations
------------------------------

Let $$M=\langle Q,\Gamma,b,\Sigma,\Delta,q_{start},F\rangle$$ be a non-deterministic single-tape Turing machine wherein $Q$ is the set of states, $\Gamma$ is the set of tape symbols, $b$ is the blank symbol, $\Sigma$ is the set of input symbols, $\Delta$ is the transition relation, $q_{start}$ is the initial state, and $F$ is the set of accepting states. The elements of the set $\{L,R,S\}$ denote, as is usual, the moves of the tape head of machine $M$.

Non-deterministic Turing machines as [[**decision procedures**]{}]{} (more precisely, programs for non-deterministic Turing machines as decision procedures) are usually defined as follows.

[[@DK00]]{} Non-deterministic Turing machine $M$ accepts input $x$ if there exists an accepting computation path of machine $M$ on input $x$.

[[@AB09]]{} \[Def:MTRejects\] Non-deterministic Turing machine $M$ rejects input $x$ if all the computation paths of machine $M$ on input x are finite and these paths are not accepting computation paths.

[[@DK00]]{} Non-deterministic Turing machine $M$ decides a language $A\subseteq\Sigma^*$ if machine $M$ accepts each word $x\in A$ and rejects each word $x\notin A$.

The time (space) computational complexity of non-deterministic Turing machine $M$ is polynomial if there exists a polynomial $t(n)$ ($s(n)$ accordingly) such that for any input $x$

1.  [the minimum of the lengths of all the accepting computation paths of machine $M$ on input $x$ does not exceed $t(|x|)$ (accordingly, the number of the different visited cells on each accepting computation path does not exceed $s(|x|)$) if machine $M$ accepts input $x$, and]{}

2.  [the lengths of all the computation paths of machine $M$ on input $x$ do not exceed $t(|x|)$ (accordingly, the number of the different visited cells on each computation path does not exceed $s(|x|)$) if machine $M$ rejects input $x$.]{}

Here, (as is usual) by means of $|x|$ the length of word $x$ is specified. Let $\mu$ be an integer.

Computation path $p$ of Turing machine $M$ on input $x$ is said to be a $\mu$-length computation path if the length of $p$ is equal to $\mu$. Accepting computation path $p$ of machine $M$ on input $x$ is said to be a $\mu$-length accepting computation path if $p$ is $\mu$-length computation path.

Computation path $p$ of Turing machine $M$ on input $x$ is said to be a $\mu_{\le}$-length ($\mu_{>}$-length) computation path if the length of $p$ is less than or equal to $\mu$ (is greater than $\mu$). Accepting computation path $p$ of machine $M$ on input $x$ is said to be a $\mu_{\le}$-length accepting computation path if $p$ is a $\mu_{\le}$-length computation path.

If Turing machine $M$ accepts input $x$ and the time complexity of machine $M$ is bounded above by polynomial $t(n)$, then the computation tree of machine $M$ on input $x$ has at least one $t(|x|)_{\le}$-length accepting computation path.

If Turing machine $M$ rejects input $x$ and the time complexity of machine $M$ is bounded above by polynomial $t(n)$ then all the computation paths of machine $M$ on input $x$ are precisely the $t(|x|)_{\le}$-length computation paths, and these paths are not accepting computation paths.

Let’s note that there are some differences between the definitions of how non-deterministic Turing machine rejects the input. Usually, non-deterministic Turing machines are defined in such a way that it is acceptable that there are some endless computation paths or $t(n)_{>}$-length computation paths in the case Turing machine rejects the input [@DK00; @GJ79; @Papa94; @G08]; sometimes definition \[Def:MTRejects\], which is stronger than the definitions in [@DK00; @GJ79; @Papa94; @G08], is used [@AB09].

Non-deterministic computations are often defined as [[**guess-and-verify**]{}]{} computations [@K72; @DK00] or [[**search-and-check**]{}]{} computations [@lL73; @G08]. In [@ClayCook], the [[**P**]{}]{} vs. [[**NP**]{}]{} Problem is formulated precisely in terms of [[**guess-and-verify**]{}]{} computations, but it is known [@DK00; @G08] that these definitions of non-deterministic computations are equivalent to the definition, which is used in the present paper, of non-deterministic computations in terms of non-deterministic Turing machines.

Notations for graphs
--------------------

Let $G=(V,E)$ be a direct acyclic graph.

Let $Nodes\langle G\rangle$ be set $V$.

Let $Edges\langle G\rangle$ be set $E$.

Let $RootNode\langle G\rangle$ be the root node of graph $G$.

For each node $u\in V$ let, as is usual, $$\begin{aligned}
&\delta^{-}(u)=\{(v,u)\ |\ ((v\in V)\wedge ((v,u)\in E))\}\
\text{be the set of all in-edges of node}\ u,\ \text{and}\\
&\delta^{+}(u)=\{(u,v)\ |\ ((v\in V)\wedge ((u,v)\in E))\}\
\text{be the set of all out-edges of node}\ u.\end{aligned}$$ Let $G=(V,E)$ be a direct acyclic graph with source node $s$ and sink node $t$.

A path $p$ in graph $G$ is said to be $s$-$t$ path if $p$ starts with the source node $s$ and ends with the sink node $t$.

A path $p$ in graph $G$ is said to be $u$-$v$ path if $p$ starts with node $u$ and ends with node $v$.

Let $PathSet\langle(u,v)\rangle$, wherein $u$ and $v$ are nodes, be the set of $u$-$v$ paths in graph $G$.

Let $AllPaths\langle G\rangle$ be the set of all the $s$-$t$ paths in graph $G$.

Let $Subgraph\langle G,P\rangle$, wherein $P$ is a path set in $G$, be graph $(V\langle sub\rangle,E\langle sub\rangle)$ such that $$\begin{aligned}
&V\langle sub\rangle=\{u\ |\ ((u\in V)\wedge(\exists p\in P :
u\in p))\}\ \text{and}\\
&E\langle sub\rangle=\{e\ |\ ((e\in E)\wedge(\exists p\in P :
e\in p))\}.\end{aligned}$$

Let $Subgraph\langle G,(u,v)\rangle$ be subgraph $$Subgraph\langle G,PathSet\langle (u,v)\rangle\rangle.$$

Network flows
-------------

Let $G=(V,E)$ be a direct acyclic graph. Network flow equations for $G$ are defined as follows [@CLRS09]:

1.  [functions $F$ from $V$ to rationals and $H$ from $E$ to rationals are introduced;]{}

2.  [for each $v\in V$, $v\ne s$, $$\begin{aligned}
    \label{Eq:LPEqs1}
    F[v]= \sum_{(u,v)\in \delta^{-}(v)} H[(u,v)];\end{aligned}$$ ]{}

3.  [for each $u\in V$, $u\ne t$, $$\begin{aligned}
    \label{Eq:LPEqs2}
    F[u]= \sum_{(u,v)\in \delta^{+}(u)} H[(u,v)].\end{aligned}$$ ]{}

Functions $F$ and $H$ in equations and are denoted by $F$-functions and $H$-functions accordingly.

Construction of deterministic multi-tape Turing\
machine $M\langle\exists AcceptingPath\rangle$
================================================

In this section, the components and the program of machine $M\langle\exists AcceptingPath\rangle$ are constructed in detail.

Underlying elements of machine $M\langle\exists AcceptingPath\rangle$
---------------------------------------------------------------------

\[SubSec:UnderlElems\]

### Sequences of computation steps

The notion of sequences of computation steps is used to define the general set of the tape-arbitrary paths which includes the set of the computation paths of machine $M$.

#### Computation steps.

Computation step $t$ of machine $M$ is defined to be tuple $$(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)})$$ wherein $d=((q,s),(q',s',m))\in\Delta$, $m\in \{L,R,S\}$, and $\kappa^{(tape)}$ and $\kappa^{(step)}$ are integers. In that case, we write $d\bigtriangleup t$.

\[Def:SequentialPair\] Let $$\begin{aligned}
&t_1=(q_{1},s_{1},q'_{1},s'_{1},m_{1},\kappa^{(tape)}_1,\kappa^{(step)}_1)\ \text{and}\
t_2=(q_{2},s_{2},q'_{2},s'_{2},m_{2},\kappa^{(tape)}_2,\kappa^{(step)}_2)\end{aligned}$$ be computation steps. Pair $(t_1,t_2)$ is said to be a sequential pair if $q_2=q_1'$, $\kappa^{(step)}_2=\kappa^{(step)}_1+1$, and

1.  [if $m_{1}=L$ then $\kappa^{(tape)}_2=\kappa^{(tape)}_1-1$;]{}

2.  [if $m_{1}=R$ then $\kappa^{(tape)}_2=\kappa^{(tape)}_1+1$;]{}

3.  [if $m_{1}=S$ then $\kappa^{(tape)}_2=\kappa^{(tape)}_1$.]{}

Only finite sequences of the computation steps, such that each pair $(t_i,t_{i+1})$ of computation steps is a sequential pair, are considered.

Pair of computation steps $$\begin{aligned}
&t_{i_1}=(q_{i_1},s_{i_1},q'_{i_1},s'_{i_1},m_{i_1},
\kappa^{(tape)}_{i_1},\kappa^{(step)}_{i_1})\ \text{and}\
t_{i_2}=(q_{i_2},s_{i_2},q'_{i_2},s'_{i_2},m_{i_2},
\kappa^{(tape)}_{i_2},\kappa^{(step)}_{i_2})\end{aligned}$$ is said to be a tape-consistent pair of computation steps if $s_{i_2}=s_{i_1}'$. Otherwise (when $s_{i_2}\ne s_{i_1}'$) the pair is said to be a tape-inconsistent pair of computation steps.

Let’s note that it is not required in this definition for computation steps $t_{i_1}$ and $t_{i_2}$ that $t_{i_2}$ follows immediately $t_{i_1}$ in computation paths of machine $M\langle\exists AcceptingPath\rangle$; there can be a sequence like $(\ldots,t_{i_1},\ldots,t_{i_2},\ldots)$.

Pair of computation steps $t_{i_1}$ and $t_{i_2}$ is said to be a tape-inconsistent pair if it is not a tape-consistent pair.

#### Auxiliary notations and definitions.

Let’s enumerate the tape cells of Turing machine $M$ on input $x$ as follows: The number of the cell $c_1$, containing the leftmost symbol of input $x$, is $1$, the number of the cell to the right of $c_1$ is $2$, the number of the cell to the left of $c_1$ is $0$, and so on.

The tape cell with number $\kappa$ is denoted by $c_{\kappa}$.

Let $x$ be an input of machine $M$. The symbol in tape cell $c_{\kappa}$ is denoted by $Tape\langle x,\kappa\rangle$.

$TapeLBound\langle \mu\rangle=2-\mu$; $TapeRBound\langle\mu\rangle=\mu$.

Integer range $[TapeLBound\langle \mu\rangle..TapeRBound\langle \mu\rangle]$ of cell numbers is denoted by $TapeRange\langle x,\mu\rangle$.

Subsequence $\omega_{sub}=(t_1,\ldots t_{\mu})$ of sequence $\omega$ of the computation steps, denoted by $Subseq\langle \omega,\kappa\rangle$, is said to be a subsequence at cell $c_{\kappa}$ of sequence $\omega$ if $\kappa^{(tape)}=\kappa$ for each computation step $t=(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)})$ in $\omega_{sub}$.

We say that sequence $\omega=(t_1,\ldots t_{\mu})$ of the computation steps starts on input $x$ if $t_1=(q_{start},s,q',s',m,1,1)$ for some $s$, $q'$, $s'$, and $m$.

We say that sequence $\omega=(t_1,\ldots t_{\mu})$ of the computation steps corresponds to input $x$ at cell $c_{\kappa^{(tape)}}$ if one of the following holds:

1.  [if $$Subseq\langle \omega,\kappa^{(tape)}\rangle=(t_{i_1},\ldots t_{i_k})\
    \text{and}\ t_{i_1}=(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)}),$$ then $s=Tape\langle x,\kappa^{(tape)}\rangle$;]{}

2.  [$Subseq\langle \omega,\kappa^{(tape)}\rangle$ is an empty sequence.]{}

Let set $$U=\{j\ |\ (t=(q,s,q',s',m,\kappa^{(tape)},j)\in \omega)\},$$ wherein $\omega$ is a sequence of computation steps, is not empty. In that case, value $\kappa=\min\{j\ |\ j\in U\}$ is denoted by $$TapeFirst\langle \omega,\kappa^{(tape)}\rangle.$$

Let set $$U=\{j\ |\ ((j<\kappa^{(step)})
\ \wedge\ (t=(q,s,q',s',m,\kappa^{(tape)},j)\in \omega))\},$$ wherein $\omega$ is a sequence of computation steps, is not empty. In that case, value $\kappa=\max\{j\ |\ j\in U\}$ is denoted by $$TapePrev\langle \omega,\kappa^{(tape)},\kappa^{(step)}\rangle.$$

Sequence $\omega=(t_1,\ldots t_{\mu})$ of the computation steps of machine $M$ is said to be $q'$-sequence of the computation steps if $$t_{\mu}=(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)}).$$

Sequence $\omega$ of the computation steps of machine $M$ is said to be an accepting sequence of the computation steps if $\omega$ is $q$-sequence wherein $q\in F$.

Sequence $\omega=(t_1,\ldots t_{\mu})$ of the computation steps of machine $M$ is said to be a $\mu$-length sequence of the computation steps.

Sequence $\omega=(t_1,\ldots t_{j})$ of the computation steps of machine $M$ is said to be a $\mu_{\le}$-length sequence of the computation steps if $j\le\mu$.

Let’s note that $\kappa^{(tape)}\in TapeRange\langle x,\mu\rangle$ for each computation step $$t=(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)})$$ in a $\mu$-length sequence of the computation steps.

Let computation step $$t=(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)}).$$ State $q$ in $t$ is denoted by $t.q$ (the same is for other elements of the tuple).

#### Kinds of sequences of computation steps.

\[Def:TapeConsistSeq\] Sequence $\omega=(t_1,\ldots t_{\mu})$ of the computation steps of machine $M$ on input $x$ is said to be a tape-consistent sequence of the computation steps on input $x$ if the following holds:

1.  [$\omega$ starts on input $x$;]{}

2.  [$\omega$ corresponds to input $x$ at each cell $\kappa\in TapeRange\langle x,\mu\rangle$;]{}

3.  for each $\kappa\in TapeRange\langle x,\mu\rangle$ the following holds:

    1.  [if subsequence $\omega_{sub}=Subseq\langle \omega,\kappa\rangle$ is not empty, then each pair $(t_i,t_{i+1})$ in $\omega_{sub}$ is a tape-consistent pair of computation steps.]{}

\[Def:TapeInconsistSeq\] Sequence $\omega=(t_1,\ldots t_{\mu})$ of the computation steps of machine $M$ on input $x$ is said to be a tape-inconsistent at pair $(\kappa^{(tape)},\kappa^{(step)})$ sequence of the computation steps on input $x$ if the following holds:

1.  [$t=(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)})\in \omega$;]{}

2.  [$\omega$ starts on input $x$;]{}

3.  one of the following holds:

    1.  [if $\kappa^{(step)}=TapeFirst\langle \omega,\kappa^{(tape)}\rangle$ then $s\ne Tape\langle x,\kappa^{(tape)}\rangle$;]{}

    2.  [if there exists $\kappa$ such that $\kappa=TapePrev\langle \omega,\kappa^{(tape)},\kappa^{(step)}\rangle$, then pair $(t_{\kappa},t_{\kappa^{(step)}})$ is a tape-inconsistent pair of the computation steps.]{}

Sequence $\omega=(t_1,\ldots t_{\mu})$ of the computation steps of machine $M$ on input $x$ is said to be a tape-inconsistent sequence of computation step on input $x$ if $\omega$ is tape-inconsistent at some pair $(\kappa^{(tape)},\kappa^{(step)})$ sequence on input $x$.

Sequence $\omega=(t_1,\ldots t_{\mu})$ of the computation steps of machine $M$ on input $x$ is said to be a tape-arbitrary sequence of the computation steps if $\omega$ starts on input $x$.

Tape-consistent sequence $\omega=(t_1,\ldots t_{\mu})$ of the computation steps is said to be the sequence corresponding to computation path $P=\alpha_1\ldots\alpha_{\mu}$ of machine $M$ on input $x$ if

1.  [each $d_i$ for $i\in[1..(\mu-1)]$, such that $d_i\bigtriangleup t_i$, is the transition corresponding to configuration transition $\alpha_i\vdash \alpha_{i+1}$, and]{}

2.  [$t_{\mu}=(q,s,q,s,S,\kappa^{(tape)},\kappa^{(\mu)})$; ‘extra’ computation step $t_{\mu}$ is added to sequence $\omega$ for simplicity of the definitions. ]{}

Tree $T$ of the computation steps is said to be the $\mu$-length ($\mu_{\le}$-length) tape-arbitrary tree of the computation steps of machine $M$ on input $x$ if each root-leaves path in $T$ is a tape-arbitrary sequence of the computation steps of machine $M$ on input $x$, and the tree contains all the $\mu$-length ($\mu_{\le}$-length) tape-arbitrary sequence of the computation steps.

#### A figure to explain the notion.

The notion of sequences of computation steps is explained in Figure \[Fig:CompStepsSeqs\]; there

1.  [the pair of computation steps $$\begin{aligned}
    s_{2,8}=(q_{i_1},a,q_{i_1}',b,L,2,8)\ and\ s_{2,14}=(q_{i_2},b,q_{i_2}',c,R,2,14)\end{aligned}$$ is a tape-consistent pair of the computation steps;]{}

2.  [the pair of computation steps $$\begin{aligned}
    s_{4,4}=(q_{i_3},x_{4},q_{i_3}',d,R,4,4)\ and\ s_{4,6}=(q_{i_4},e,q_{i_4}',f,L,4,6),\end{aligned}$$ wherein $e\ne d$, is a tape-inconsistent pair of the computation steps.]{}

![A sequence of computation steps.[]{data-label="Fig:CompStepsSeqs"}](Images/Seqs.eps){height="8cm"}

#### Sequences of computation steps in graphs (trees).

Let $G=(V,E)$ be a graph (tree) such that for each node $u\in V$ a computation step of machine $M\langle NP\rangle$ is associated with node $u$.

The computation step of machine $M\langle NP\rangle$ associated with node $u\in V$ is denoted by $u.step$.

Let $p$ be $s$-$t$ path $(u_1,\ldots,u_m)$ in graph $G$. Sequence of the computation steps $\omega=(t_1,\ldots,t_{m})$ such that $t_i=u_i.step$ for $i\in [1..m]$ is denoted by $\omega\langle p\rangle$.

Let $\omega\langle p\rangle$ be a tape-consistent (tape-consistent, tape-inconsistent) sequence of the computation steps. Path $p$ is said to be a tape-consistent (tape-consistent, tape-inconsistent) path in graph (tree) $G$.

Concept of the construction of machine $M\langle\exists AcceptingPath\rangle$
-----------------------------------------------------------------------------

\[SubSec:Concept\]

The concept of the construction of machine $M\langle\exists AcceptingPath\rangle$ is based on the following proposition.

\[Prop:TConsToCompPaths\] There is one-to-one mapping from the set of the $\mu$-length tape-consistent sequences of the computation steps of machine $M$ on input $x$ onto the set of the $\mu$-length sequences of the computation steps of machine $M$ on input $x$ that correspond to the $\mu$-length computation paths of machine $M$ on input $x$.

The proposition follows directly from the definition of sequences of the computation steps.

### Definitions for sets of sequences of computation steps

Let $TConsistSeqSet\langle x,q,\mu\rangle$ be the set of $\mu$-length tape-consistent $q$-sequences of the computation steps of machine $M$ on input $x$.

Let $TInconsistSeqSet\langle x,q,\mu\rangle$ be the set of the $\mu$-length tape-inconsistent $q$-sequences of the computation steps of machine $M$ on input $x$.

Let $TArbitrarySeqSet\langle x,q,\mu\rangle$ be the set of the $\mu$-length tape-arbitrary $q$-sequences of the computation steps of machine $M$ on input $x$.

$Q\langle Any\rangle=Q\setminus \{q_{start}\}$.

$$TConsistSeqSet\langle x,S,\mu\rangle=\cup_{q\in S}{TConsistSeqSet\langle x,q,\mu\rangle}$$ for some set $S$ of the states of machine $M$.

### Determining if there exists an accepting computation path

\[Prop:ArbEqConInc\] Set $$TArbitrarySeq\langle x,q,\mu\rangle$$ is the disjoint union of sets $$TConsistSeq\langle x,q,\mu\rangle$$ and $$TInconsistSeq\langle x,q,\mu\rangle.$$

The following is to be shown: $$\begin{aligned}
&TConsistSeqSet\langle x,q,\mu\rangle\cap
TInconsistSeqSet\langle x,q,\mu\rangle=\emptyset\ \text{and}\\
&TArbitrarySeqSet\langle x,q,\mu\rangle=
TConsistSeqSet\langle x,q,\mu\rangle\cup
TInconsistSeqSet\langle x,q,\mu\rangle.\end{aligned}$$

The first equality follows directly from the definitions of sequences of the computation steps.

Furthermore, inclusions $$\begin{aligned}
&TConsistSeqSet\langle x,q,\mu\rangle\subseteq
TArbitrarySeqSet\langle x,q,\mu\rangle\ \text{and}\\
&TInconsistSeqSet\langle x,q,\mu\rangle\subseteq
TArbitrarySeqSet\langle x,q,\mu\rangle\end{aligned}$$ also follow directly from the definitions of sequences of the computation steps.

The rest is to show that $$TArbitrarySeqSet\langle x,q,\mu\rangle\subseteq
TConsistSeqSet\langle x,q,\mu\rangle\cup
TInconsistSeqSet\langle x,q,\mu\rangle.$$

Let $L=(t_1,\ldots t_{\mu})$ be a tape-arbitrary sequence of the computation steps. Then

1.  [if one of 3.1) and 3.2) in definition \[Def:TapeInconsistSeq\] holds for some $t_i\in L$ then $$L\in TInconsistSeqSet\langle x,q,\mu\rangle;$$]{}

2.  [otherwise, $L\in TConsistSeqSet\langle x,q,\mu\rangle$.]{}

Proposition \[Prop:ArbEqConInc\] is not used directly in the construction of machine $M\langle\exists AcceptingPath\rangle$; this proposition is used just to show that the set of the tape-consistent sequences is considered as a subset of the more general set of the tape-arbitrary sequences.

Let $M\langle NP\rangle$ be a non-deterministic single-tape Turing machine that decides language $A$ and works in time $t(n)$. To determine if there exists a tape-consistent sequence of the computation steps, the following is performed:

1.  [construct non-deterministic multi-tape Turing machine $M\langle TArbitrarySeqs\rangle$ such that there is one-to-one mapping from the set of the root-leaves paths in the computation tree of machine $M\langle TArbitrarySeqs\rangle$, denoted by $TArbitrarySeqTree$, to the set of the root-leaves paths in the $\mu_{\le}$-length tape-arbitrary tree of the computation steps of machine $M\langle NP\rangle$ on input $x$;]{}

2.  construct a direct acyclic graph $TArbitrarySeqGraph$ of the nodes of tree $TArbitrarySeqTree$ as a result of deep-first (or breadth-first) traversal of tree $TArbitrarySeqTree$ such that there is one-to-one mapping from the set of the $s$-$t$ paths in graph $TArbitrarySeqGraph$ onto the set of the root-leaves paths in the $\mu$-length tape-arbitrary tree of the computation steps of machine $M\langle NP\rangle$ on input $x$; the features of the construction is as follows:

    1.  [Turing machine $M\langle NP\rangle$ does not run explicitly, so the computation tree of machine $M\langle TArbitrarySeqs\rangle$ is not built explicitly,]{}

    2.  [the size of graph $TArbitrarySeqGraph$ is polynomial in $|x|$ wherein $|x|$ is the length of the input;]{}

3.  [consider graph $TArbitrarySeqGraph$ as the direct acyclic control flow graph $TArbSeqCFG$ of a deterministic computer program that writes values to the tape cells and reads values from the tape cells of machine $M\langle NP\rangle$;]{}

4.  [using reaching definitions analysis [@NNH05] on graph $TArbSeqCFG$ and on the set of the assignments to the tape cells and the set of the usages of the tape cells, compute the tape-consistent pairs of the computation steps;]{}

5.  [using the results of reaching definitions analysis, reduce the problem of determining if there exists an accepting tape-consistent path in the control flow graph to problem [[**LP**]{}]{}; use polynomial time algorithm to solve problem [[**LP**]{}]{} [@Kh80; @K84];]{}

6.  [because proposition \[Prop:TConsToCompPaths\] holds, there is one-to-one mapping from the tape-consistent accepting paths to the accepting computation paths of machine $M\langle NP\rangle$; so one can determine if there exists an accepting computation path of machine $M\langle NP\rangle$.]{}

These steps are based on the following key feature of tape-arbitrary sequences of the computation steps.

To say informally, if a path in computation tree $TArbitrarySeqTree$ starts in some node then the segment of the path from the node to a leaf does not depend on the segment of the path from the source to the node. Therefore, all the subtrees of computation tree $TArbitrarySeqTree$ that start at the equal nodes are the same, and the set of the paths in the tree can be represented as the set of the paths in a graph.

So, to construct graph $TArbitrarySeqGraph$, computation tree $TArbitrarySeqTree$ is not built explicitly; instead, the steps of machine $M\langle TArbitrarySeqs\rangle$ are simulated to construct the nodes of the tree and to construct the graph at the same time. If computation tree $TArbitrarySeqTree$ has $r$ subtrees that start with a node $u$ then $(r-1)$ subtrees are cut; therefore, the paths in the subtrees are not duplicated in the graph.

The reason why the size of graph $TArbitrarySeqGraph$ is polynomial in $|x|$ is the following:

1.  [to compute the elements of a tape-consistent sequence of the computation steps of machine $M\langle NP\rangle$, one should keep all the symbols written on the tape of machine $M\langle NP\rangle$; therefore in that case one uses polynomial space and exponential time;]{}

2.  [if one computes the elements of a tape-arbitrary sequence of computation steps of machine $M\langle NP\rangle$, one should know the current computation step only; therefore, in that case, one uses logarithmic space and polynomial time.]{}

The construction of graph $TArbitrarySeqGraph$ is explained in Figure \[Fig:TArbSeqGrConstr\]; there

1.  [$TAST$ is the shortened indication of $TArbitrarySeqTree$,]{}

2.  [$TASG$ is the shortened indication of $TArbitrarySeqGraph$,]{}

3.  [subtree that is cut is orange-colored, and]{}

4.  [new edge in graph $TArbitrarySeqGraph$ is green-colored.]{}

![Construction of graph $TArbitrarySeqGraph$.[]{data-label="Fig:TArbSeqGrConstr"}](Images/TArbSeqGrConstr.eps){height="6cm"}

### How machine $M\langle\exists AcceptingPath\rangle$ works

Turing machine $M\langle\exists AcceptingPath\rangle$ works as follows. It performs a loop for $\mu$, $1\le\mu\le (t(n)+1)$, determining at each iteration if there $$\begin{aligned}
\exists \omega\,(\omega\in TConsistSeqSet\langle x,S,\mu\rangle\rangle)\end{aligned}$$ wherein $S$ is a set of the states of machine $M\langle NP\rangle$. Since machine $M\langle NP\rangle$ works in time $t(n)$, one of the following happens:

1.  [if machine $M\langle NP\rangle$ accepts input $x$, $|x|=n$, then the loop stops at iteration $\mu\le t(n)$ such that $$\exists p\,(p\in TConsistSeqSet\langle x,F,\mu\rangle\rangle)$$ holds;]{}

2.  [if machine $M\langle NP\rangle$ rejects input $x$, $|x|=n$, then the loop stops at iteration $\mu\le (t(n)+1)$ such that $$|TConsistSeqSet\langle x,Q\langle Any\rangle,\mu\rangle\rangle|=0.$$ ]{}

If $t(n)$ is a polynomial, then machine $M\langle\exists AcceptingPath\rangle$ works in polynomial time in $t(n)$ and therefore works in polynomial time in $n$ wherein $n=|x|$.

If machine $M\langle NP\rangle$ works according to definition \[Def:MTRejects\], both to accept and to reject the input of machine $M\langle NP\rangle$, polynomial $t(n)$ is not used in the program of machine $M\langle\exists AcceptingPath\rangle$. Machine $M\langle\exists AcceptingPath\rangle$ should use polynomial $t(n)$ to reject the input if machine $M\langle NP\rangle$ works according to the weaker definitions [@DK00; @GJ79; @Papa94; @G08].

Differences from reduction $L\le_{m}^{P}{\text{\bf 3-CNF-SAT}}$ in detail
-------------------------------------------------------------------------

Let $L$ be a language from class [[**NP**]{}]{}. The features of reduction $L\le_{m}^{P}{\text{\bf 3-CNF-SAT}}$ [@C71] in detail compared to the solution suggested in the present paper are the following:

1.  [reduction $L\le_{m}^{P}{\text{\bf 3-CNF-SAT}}$ sets in fact one-to-one mapping between the set of the assignments that satisfy a Boolean formula and the set of the tape-consistent sequences of computation steps;]{}

2.  [in reduction $L\le_{m}^{P}{\text{\bf 3-CNF-SAT}}$, the set of the tape-consistent sequences of the computation steps is a subset of the set of the paths in a graph which is implicitly constructed ($P_{s,t}^{j}$ [@C71 page 153] are some nodes of this graph);]{}

3.  [an assignment that does not satisfy a Boolean formula can correspond to sequences of the computation steps that do not correspond to computation paths, so there is no one-to-one mapping between the set of such assignments and the set of the tape-inconsistent sequences of the computation steps.]{}

Thus, the difference between the solution suggested in the present paper and reduction $L\le_{m}^{P}{\text{\bf 3-CNF-SAT}}$ is as follows.

Reduction $L\le_{m}^{P}{\text{\bf 3-CNF-SAT}}$ is in fact based on the notion of tape-consistent sequences of the computation steps; in reduction $L\le_{m}^{P}{\text{\bf 3-CNF-SAT}}$, tape-consistent sequences are not considered as a subset of the more general set of tape-arbitrary sequences of the computation steps.

In contrast, the solution suggested in the present paper is based on the concept of the set of tape-arbitrary sequences of the computation steps that consists of the set of tape-consistent sequences and the set of tape-inconsistent sequences. It turns out it takes polynomial time to determine if there exists an accepting computation path using this concept.

Regarding reduction of problem [[**3-CNF-SAT**]{}]{} to integer linear programming (for example, problem [[**0-1 ILP**]{}]{} [@K72], and problem [[**Simple D2CIF**]{}]{} [@EIS76]), exponential time algorithms for problem [[**ILP**]{}]{} are only known for now.

Program of machine $M\langle\exists AcceptingPath\rangle$
---------------------------------------------------------

### Non-deterministic multi-tape Turing machine $M\langle TArbitrarySeqs\rangle$

Turing machine $M\langle TArbitrarySeqs\rangle$ is constructed as follows:

1.  [the input of the machine is a word $(x,\mu)$, wherein $x$ is a word in alphabet $\Sigma$ and $\mu$ is a binary positive integer;]{}

2.  [the machine has one accepting state $q_{A}$ and state $q_{R}$, $q_{R}\ne q_{A}$, referred to as rejecting state.]{}

[Turing machine $M\langle TArbitrarySeqs\rangle$]{} Word $(x,\mu)$\
\
each $\kappa^{(step)}\in [1..\mu]$\
\
$\kappa^{(step)}=\mu$\
\
\
\
\
\
$\kappa^{(step)}=1$\
\
[compute non-deterministically computation step $$t_1=(q_{start},s,q',s',m,1,1)$$ of machine $M\langle NP\rangle$ wherein $s=Tape\langle x,1\rangle$]{}\
\
[by computation step $$t_{\kappa^{(step)}}=(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)}),$$ compute non-deterministically computation step $$t_{\kappa^{(step)}+1}=(q',s'',q'',s''',m',\kappa^{(tape+1)},\kappa^{(step)}+1)$$ of machine $M\langle NP\rangle$ such that definition \[Def:SequentialPair\] holds]{}\
\
\
\
\
\
\
\

There is one-to-one mapping from the set of the root-leaves accepting paths in computation tree $TArbitrarySeqTree$, which is the computation tree of machine $M\langle TArbitrarySeqs\rangle$, to the set of the root-leaves paths in the $\mu_{\le}$-length tape-arbitrary tree of the computation steps of machine $M\langle NP\rangle$ on input $x$.

The time complexity of non-deterministic Turing machine $M\langle TArbitrarySeqs\rangle$ is polynomial in $\mu$, and the space complexity is logarithmic in $\mu$.

Values $\kappa^{(tape)}$ and $\kappa^{(step)}$, contained in the computation steps of a $\mu$-length sequence of the computation steps, are binary integers such that $\operatorname{abs}(\kappa^{(tape)})\le\mu$ and $\kappa^{(step)}\le\mu$, so the proposition holds.

### Deterministic algorithm $ConstructTArbitrarySeqGraph$

To construct graph $TArbitrarySeqGraph$, the algorithm performs deep-first traversal of computation tree $TArbitrarySeqTree$. The constructed graph is a direct acyclic graph of polynomial size; it has one source node and a set of bottom nodes. As it is explained in subsection \[SubSec:Concept\], computation tree is not build explicitly in the algorithm of the construction of graph $TArbitrarySeqGraph$.

Breadth-first traversal of tree $TArbitrarySeqTree$ can be also used to construct the graph.

[$ConstructTArbitrarySeqGraph$]{} Root node $r$ of tree $TArbitrarySeqTree$ Graph $TArbitrarySeqGraph$\
\
set $VisitedNodeSet:=\emptyset$\
graph $G:=(\emptyset,\emptyset)$\
\
\
$DFTConstructGraphFromNode(r)$\
\
(graph $G$)

[$DFTConstructGraphFromNode$]{} Node $u$ of tree $TArbitrarySeqTree$ Set $VisitedNodeSet$, graph $G$\
\
$\exists u'(u'\in VisitedNodeSet)$ such that $u'.step=u.step$\
\
\
\
\
\
[add $u$ to $VisitedNodeSet$]{}\
[add $u$ to $Nodes\langle G\rangle$]{}\
\
\
each edge $(u,v)\in \delta^{+}(u)$\
\
$DFTConstructGraphFromNode(v)$\
[add edge $(u,v)$ to $Edges\langle G\rangle$]{}\

Let’s note that deep-first traversal, which is a recursive algorithm, of tree $TArbitrarySeqTree$ can be simulated on a deterministic multi-tape Turing machine using a non-recursive algorithm.

There is one-to-one mapping from the set of the $s$-$t$ paths in direct acyclic graph $TArbitrarySeqGraph$ to the set of the root-leaves paths in the $\mu$-length tape-arbitrary tree of the computation steps of machine $M\langle NP\rangle$ on input $x$.

The count of the nodes in graph $TArbitrarySeqGraph$ is polynomial in $\mu$.

Values $\kappa^{(tape)}$ and $\kappa^{(step)}$, contained in the computation steps of a $\mu$-length sequence of the computation steps, are binary integers such that $\operatorname{abs}(\kappa^{(tape)})\le\mu$ and $\kappa^{(step)}\le\mu$. Therefore, the count of the nodes in graph $TArbitrarySeqGraph$ is ${\mathsf{O}}\left(2^{C\cdot\log(\mu)}\right)$ (total count of different computation steps of $\mu$-length sequences) which is ${\mathsf{O}}\left(\mu^{C}\right)$. So the proposition holds.

So, the count of the nodes in computation $TArbitrarySeqTree$ can be exponential in $\mu$, but the count of the nodes in graph $TArbitrarySeqGraph$ is polynomial in $\mu$.

The time complexity of deterministic algorithm $$ConstructTArbitrarySeqGraph$$ is polynomial in $\mu$.

### Deterministic algorithm $ComputeTConsistPairSet$

The set of pairs $(u,v)$ of the nodes of graph $TArbitrarySeqGraph$, such that pair $(u.step,v.step)$ is a tape-consistent pair of computation steps, is denoted by $TConsistPairSet$.

Algorithm $ComputeTConsistPairSet$ computes set $TConsistPairSet$.

The algorithm considers graph $TArbitrarySeqGraph$ as an acyclic control flow graph $$TArbSeqCFG$$ of a deterministic computer program that writes values to the tape cells and reads values from the tape cells of machine $M\langle NP\rangle$. Namely, each computation step $$t=(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)})$$ in $Nodes\langle TArbSeqCFG\rangle$ is treated as the usage of symbol $s$ in the tape cell with number $\kappa^{(tape)}$ and the assignment of symbol $s'$ to this tape cell.

To be used further, graph $TArbSeqCFG$ is preliminarily transformed as follows:

1.  create in graph $TArbSeqCFG$ source node $s$, and add edge $(s,RootNode\langle TArbSeqCFG\rangle))$; add to node $s$ a special assignment which is treated as the assignment of the following symbols to each cell of the tape of machine $M\langle NP\rangle$ when the machine starts:

    1.  [input symbols for cells $c_{\kappa}$ wherein $\kappa\in[1..|x|]$, and]{}

    2.  [blank symbol for cells $c_{\kappa}$ wherein $\kappa\notin[1..|x|]$;]{}

2.  [ create in graph $TArbSeqCFG$ sink node $t$; connect $t$ with the bottom nodes $u$ such that $u.step$ contains a state $q\in S$ wherein $S$ is a set of the states of machine $M\langle NP\rangle$; it is used in such a way that the computation paths of machine $M\langle NP\rangle$ ending with the states from $S$ are only considered; ]{}

3.  [add to node $t$ a special ‘extra’ usage in such a way that if an assignment $\eta$ reaches node $t$ then there is a tape consistent pair $(\eta.step,t.step)$; this usage is used for simplicity of linear program [[**TCPELP**]{}]{} deffined below; ]{}

4.  [remove all the simple chains in graph $TArbSeqCFG$ (they do not end with the sink node $t$) as it is shown in Figure \[Fig:CutChains\]; there $TASCFG$ is the shortened indication of $TArbSeqCFG$, $q_{A}$ is an accepting state, $q_{R}$ is a rejecting state, and the elements of the graph that are removed are red-colored.]{}

![Removing the simple chains.[]{data-label="Fig:CutChains"}](Images/CutChains.eps){height="6cm"}

[$ComputeTConsistPairSet$]{} Graph $TArbSeqCFG$ Set $TConsistPairSet$\
\
set $TConsistPairSet:=\emptyset$\
\
\
[enumerate all the assignments to the tape cells in nodes $Nodes\langle TArbSeqCFG\rangle$]{}\
[enumerate all the usages of the tape cells in nodes $Nodes\langle TArbSeqCFG\rangle$]{}\
\
[using the reaching definitions analysis on control flow graph $TArbSeqCFG$ and on the sets of assignments and usages, compute set $DefUsePairSet$ of the def-use pairs]{}\
[call $ProcessDefUsePairSet$]{}\
\
$TConsistPairSet$

[$ProcessDefUsePairSet$]{} Graph $TArbSeqCFG$, set $DefUsePairSet$ Set $TConsistPairSet$\
each pair $(def,use)\in DefUsePairSet$\
\
\
pair $(node_{def}.step,node_{use}.step)$ is a pair such that definition \[Def:TapeConsistSeq\] holds\
\
[add pair $(node_{def},node_{use})$ to $TConsistPairSet$]{}\
\
$node_{use}=t$\
\
[add pair $(node_{def},node_{use})$ to $TConsistPairSet$]{}\
\

The time complexity of deterministic algorithm $$ComputeTConsistPairSet$$ is polynomial in $\mu$.

The time complexity of the reaching definition analysis is polynomial in the count of the nodes and the count of the edges in the control flow graph, so the proposition holds.

### Deterministic algorithm $DetermineIfExistsTConsistSeq$

The problem of determining if there $$\exists \omega\,(\omega\in TConsistSeqSet\langle x,F,\mu\rangle)$$ is denoted by [[[**TCPEP**]{}]{} (Tape-Consistent Path Existence Problem)]{}.

Algorithm $DetermineIfExistsTConsistSeq$ solves problem [[**TCPEP**]{}]{} using linear program formulation. The input of the algorithm is tuple $(TArbSeqCFG,TConsistPairSet)$; the algorithm determines if there exists a path $p$ in graph $TArbSeqCFG$ such that $\omega\langle p\rangle$ is a tape-consistent sequence of the computation steps.

#### Commodities for tape-consistent pairs.

Let

1.  [integer $k=|TConsistPairSet|$;]{}

2.  [integer segment $CommSeg$ be $[1..k]$;]{}

3.  [subgraphs $$G_i=Subgraph\langle TArbSeqCFG, (u_i,v_i)\rangle$$ for each $i\in CommSeg$ wherein $(u_i,v_i)\in TConsistPairSet$;]{}

4.  [$V_i$ be $Nodes\langle G_i\rangle$ and $E_i$ be $Edges\langle G_i\rangle$.]{}

Commodities $$K_i(s_i,t_i),\quad i\in CommSeg,$$ in graph $TArbSeqCFG$ are defined as follows:

1.  [the set of the nodes and the set of the edges of commodity $K_i$ are $V_i$ and $E_i$ (excluding some nodes and edges as explained below);]{}

2.  [$s_i=u_i$ and $t_i=v_i$.]{}

Let’s consider nodes $d$ in $G_i$ such that definition in $d.step$ ‘hides’ the definition in $u_i$:

1.  [such nodes are contained in the paths from $u_i$ to $v_i$;]{}

2.  [$d.step.\kappa^{(tape)}=u_i.step.\kappa^{(tape)}$.]{}

These nodes are excluded to simplify linear progam defined below (excluding the nodes is shown in Figure \[Fig:ExcludeDefs\]; the excluded elements of graph $G_i$ are red-colored).

![Excluding the definitions that hides $u_{i}$.[]{data-label="Fig:ExcludeDefs"}](Images/ExcludeDefs.eps){height="7cm"}

Graphs $G_i$ without the excluded nodes can be easily computed using label propagate algorithm: It is sufficient to do the following:

1.  [propagate a label from node $u_i$ to node $v_i$, excluding nodes $d$ that hides the definition in $u_i$;]{}

2.  [propagate another label from node $v_i$ to node $u_i$ in such a way;]{}

3.  [get the intersection of the subgraphs such that their nodes are labeled.]{}

#### Definitions for linear program formulation.

Let integer segment $TapeSeg$ be $[L..R]$ wherein $$TapeLBound\langle \mu\rangle\le L\le R\le TapeRBound\langle \mu\rangle.$$

$$\begin{aligned}
TConsistPairSet\langle \zeta\rangle=\{(u,v)\ |\
(((u,v)\in TConsistPairSet) \wedge (u.step.\kappa^{(tape)}=\zeta))\}.\end{aligned}$$

$$\begin{aligned}
K\langle\zeta \rangle=\{K_i(s_i,t_i)\ | \ (s_i,t_i)\in TConsistPairSet\langle \zeta\rangle\}.\end{aligned}$$

$$CommSeg\langle \zeta\rangle=\{i\ |\ K_i(s_i,t_i)\in K\langle\zeta \rangle\}.$$

$$CommSeg\langle TapeSeg\rangle=\cup_{\zeta\in TapeSeg}CommSeg\langle \zeta\rangle.$$

$$\begin{aligned}
&V\langle tcon,u,\zeta\rangle=\{s_i\ |\ K_i(s_i,t_i)\in K\langle\zeta \rangle\},\\
&V\langle tcon,v,\zeta\rangle=\{t_i\ |\ K_i(s_i,t_i)\in K\langle\zeta \rangle\}\}.\end{aligned}$$

$V\langle tcon,\zeta\rangle=V\langle tcon,u,\zeta\rangle\cup V\langle tcon,v,\zeta\rangle$.

$E\langle tcon,\zeta\rangle=TConsistPairSet\langle \zeta\rangle$.

Graph $G\langle tcon,\zeta\rangle=(V\langle tcon,\zeta\rangle,E\langle tcon,\zeta\rangle)$.

$$D(u)=\{\zeta\ |\ ((\zeta\in CommSeg\langle TapeSeg\rangle)\wedge (u\in V\langle tcon,\zeta\rangle))\}.$$

$s$-$t$ path $$p=(s_1=s,t_1=s_2,t_2=s_3,..,t_m=t)$$ in graph $G\langle tcon,\zeta\rangle$ such that each subpath $(s_i,..,t_i)\in AllPaths\langle G_i\rangle$ is denoted by a $K$-path in graph $G\langle tcon,\zeta\rangle$.

#### Linear program formulation.

Let’s introduce the set of linear equations, denoted by $$TCPELPEqSet,$$ as follows:

1.  [for each graph $G_i$ of commodities $K_i$, $i\in CommSeg\langle TapeSeg\rangle$, network flow functions $F\langle K\rangle_i$ and $H\langle K\rangle_i$ and network flow equations and for these functions;]{}

2.  [ for each graph $G\langle tcon,\zeta\rangle$, $\zeta\in TapeSeg$, network flow functions $F\langle \mu\rangle_{\zeta}$ and $H\langle \mu\rangle_{\zeta}$ and network flow equations and for these functions; ]{}

3.  [for each node $u\in Nodes\langle TArbSeqCFG\rangle$, functions $F\langle \mu,sum\rangle_{\zeta}$ from nodes to rationals and linear equations $$\begin{aligned}
    F\langle \mu,sum\rangle_{\zeta}[u]=
    \sum_{j\in CommSeg\langle \zeta\rangle)}F\langle K\rangle_j[u];\end{aligned}$$ ]{}

4.  [ for the whole graph $TArbSeqCFG$, network flow functions $F\langle G\rangle$ and $H\langle G\rangle$ and network flow equations and for these functions; ]{}

5.  [for each node $u\in Nodes\langle TArbSeqCFG\rangle$ and for each $\zeta\in[(-\mu)..\mu]$ such that $u\in V_i$, linear equations $$\begin{aligned}
    F\langle \mu,sum\rangle_{\zeta}[u]=F\langle G\rangle[u].\end{aligned}$$ ]{}

6.  [linear equations $$\begin{aligned}
    F\langle G\rangle[s]=1,\quad F\langle G\rangle[t]=1;\end{aligned}$$ ]{}

7.  [in case $D(u)=\emptyset$, $u\ne s$ and $u\ne t$, linear equations $$F\langle \mu\rangle_{\zeta}[u]=0$$ if $u\in G_i$ and $i\in CommSeg\langle \zeta\rangle$; ]{}

8.  [in case $\delta^{+}(u)=\emptyset$ or $\delta^{-}(u)=\emptyset$ in graph $G\langle tcon,\zeta\rangle$, $u\ne s$ and $u\ne t$, linear equations $$F\langle \mu\rangle_{\zeta}[u]=0.$$ ]{}

Let’s define linear program [[**TCPELP**]{}]{} (Tape-Consistent Path Existence Linear Program) with linear equations $TCPELPEqSet$: $$\begin{aligned}
\label{Eq:TCPELPDef}
\begin{array}{ll}
\text{\bf minimize}   & 1\\
\text{\bf subject to} & (U x=b)\ \text{and}\ (x\ge {\mathsf{O}})\ \text{and}\\
& \text{(x is a fractional vector)}.
\end{array}\end{aligned}$$ An explanation of linear program \[Eq:TCPELPDef\] is shown in Figure \[Fig:DetIfExistsPath\]; there

1.  [$TASCFG$ is the shortened indication of $TArbSeqCFG$;]{}

2.  [$\omega\langle p\rangle$, wherein path $p=(s_1=s,t_1=s_2,t_2=s_3,..,t_7=t)$, is a tape-consistent sequence of the computation steps;]{}

3.  [$F\langle G\rangle[u_j]=1$ for the nodes on accepting path $p$;]{}

4.  [$p$ is a $K$-path in graph $G\langle tcon,\zeta'\rangle$, and $p$ is also a $K$-path in graph $G\langle tcon,\zeta''\rangle$;]{}

5.  [commodities $K_i(s_i,t_i)$ from $K\langle\zeta'\rangle$, such that subpath $(s_i,..,t_i)\in K_i(s_i,t_i)$, are blue-colored; commodities $K_i(s_i,t_i)$ from $K\langle\zeta''\rangle$, such that subpath $(s_i,..,t_i)\in K_i(s_i,t_i)$, are orange-colored.]{}

![An explanation of linear program \[Eq:TCPELPDef\].[]{data-label="Fig:DetIfExistsPath"}](Images/DetIfExistsPath.eps){height="6cm"}

\[Prop:TConPathExists\] There exists a solution of linear program iff there exists sequence $$\omega\langle p\rangle\in TConsistSeqSet\langle x,S,\mu\rangle$$ wherein $p$ is a $s$-$t$ path in graph $TArbSeqCFG$.

At first, let’s prove ((there exists a solution of linear program )$\,\Rightarrow\,$ (there exists a tape-consistent sequence $\omega\langle p\rangle$)).

Because equations 1)–8) hold, there exists a $K$-path $p$ in graph $G\langle tcon,\zeta\rangle$ for some $\zeta\in CommSeg$. Let’s consider a node $u\in p$ such that $u\in V\langle tcon,\zeta'\rangle$ wherein $\zeta'\ne \zeta$. Because network flow equations and hold for graph $G\langle tcon,\zeta'\rangle$ and graphs $K\langle\zeta'\rangle$, $p$ is also $K$-path in graph $G\langle tcon,\zeta'\rangle$. It means that node $v$ such that $(u,v)$ is tape-consistent pair is also in $p$. So, $\omega\langle p\rangle$ is a tape-consistent sequence of the computation steps.

Further, let’s prove ((there exists a tape-consistent sequence $\omega\langle p\rangle$)$\,\Rightarrow\,$ (there exists a solution of linear program )).

Let $F[u]=1$ and $H[(u,v)]=1$ for all the nodes in $u\in p$ and all the edges $(u,v)\in p$ wherein $F$ and $H$ are $F$- and $H$-functions in equations $TCPELPEqSet$. In that case, all the equations are satisfied.

#### Pseudocode of the algorithm.

$$TapeLeft\langle \omega\rangle=\min\{\kappa^{(tape)}\ |\
t=(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)})\in \omega\}$$ wherein $\omega$ is a sequence of the computation steps.

$$TapeRight\langle \omega\rangle=\max\{\kappa^{(tape)}\ |\
t=(q,s,q',s',m,\kappa^{(tape)},\kappa^{(step)})\in \omega\}$$ wherein $\omega$ is a sequence of the computation steps.

Algorithm $DetermineIfExistsTConsistSeq$ is based on linear program . Because $\mu$-length sequences of the computation steps are considered, there exists integer segment $TapeSeg$ such that linear program has an optimal solution iff there exists sequence $\omega\langle p\rangle\in TConsistSeqSet\langle x,S,\mu\rangle$ such that $TapeLeft\langle\omega\langle p\rangle\rangle=L$ and $TapeRight\langle\omega\langle p\rangle\rangle=R$.

[$DetermineIfExistsTConsistSeq$]{} Graph $TArbSeqCFG$, $TConsistPairSet$ If $\exists p(p\in TConsistSeqSet\langle x,S,\mu\rangle)$\
integer $i\in TapeRange\langle x,\mu\rangle$\
\
integer $j\in [i..TapeRBound\langle \mu\rangle]$\
\
[$TapeSeg:=[i..j]$]{}\
[compute constraints matrix $U$ of linear program ]{}\
[find an optimal solution of linear program ]{}\
there exists an optimal solution\
\
$\mathbf{True}$\
\
\
\
\
$\mathbf{False}$

The time complexity of deterministic algorithm $$DetermineIfExistsTConsistSeq$$ is polynomial in $\mu$.

It follows from the following:

1.  [there exist polynomial time algorithms to solve problem [[**LP**]{}]{} [@Kh80; @K84];]{}

2.  [these algorithms can be applied for linear programs such that their polyhedrons are not full-dimensional polyhedrons [@S98].]{}

It follows from algorithm $DetermineIfExistsTConsistSeq$ that an accepting computation path of machine $M\langle NP\rangle$ can be found in an explicit way: Just take a $K$-path $p$ in graph $G\langle tcon,\zeta\rangle$ for $\zeta\in TapeSeg$ such that $F\langle G\rangle[u]>0$ for each $u\in p$ and retreive the computation path by the sequence of the computation steps.

### Pseudocode of machine $M\langle\exists AcceptingPath\rangle$

Deterministic multi-tape Turing machine $M\langle\exists AcceptingPath\rangle$ is constructed using deterministic algorithms $$\begin{aligned}
&ConstructTArbitrarySeqGraph,\ ComputeTConsistPairSet,\ and\\ 
&DetermineIfExistsTConsistSeq.\end{aligned}$$

[The program of Turing machine $M\langle\exists AcceptingPath\rangle$]{} Word $x$ If there exists an accepting computation path of machine $M\langle NP\rangle$ on input $x$\
\
integer $\mu:=1$\
\
\
\
\
[graph $TArbitrarySeqGraph:=ConstructTArbitrarySeqGraph(x,\mu)$]{}\
\
[construct control flow graph $TArbSeqCFG$ wherein $S=F$]{}\
[set $TConsistPairSet:=ComputeTConsistPairSet(TArbSeqCFG)$]{}\
\
\
[$\gamma_F:=DetermineIfExistsTConsistSeq(TArbSeqCFG,TConsistPairSet)$]{}\
\
$\gamma_F$\
\
[write $\mathbf{True}$ to the output]{}\
\
\
\
[construct control flow graph $TArbSeqCFG$ wherein $S=Q\langle Any\rangle$]{}\
[set $TConsistPairSet:=ComputeTConsistPairSet(TArbSeqCFG)$]{}\
\
\
[$\gamma_{Any}:=DetermineIfExistsTConsistSeq(TArbSeqCFG,TConsistPairSet)$]{}\
\
$\neg (\gamma_{Any})$\
\
[write $\mathbf{False}$ to the output]{}\
\
\
\
$\mu+:=1$\
\
\
\
[write $\mathbf{False}$ to the output]{}

If $M\langle NP\rangle$ is a non-deterministic single-tape Turing machine that decides a language $A$, then deterministic multi-tape Turing machine $M\langle\exists AcceptingPath\rangle$ determines if there exists an accepting computation path of machine $M\langle NP\rangle$ on input $x$.

Machine $M\langle\exists AcceptingPath\rangle$ works as explained in subsection \[SubSec:Concept\], so the machine determines if there exists an accepting computation path of machine $M\langle NP\rangle$.

The time complexity of machine $M\langle\exists AcceptingPath\rangle$ is polynomial in $t(n)$.

The time complexity of the algorithms, used in the program of machine $M\langle\exists AcceptingPath\rangle$, is polynomial in $\mu$, and $\mu\in [1..(t(n)+1)]$, wherein $n=|x|$; therefore, the time complexity of the machine is polynomial in $t(n)$.

Time and space complexity of machine $M\langle\exists AcceptingPath\rangle$
---------------------------------------------------------------------------

Let $n\_count$ be $|Nodes\langle TArbitrarySeqGraph\rangle|$ and $e\_count$ be $|Edges\langle TArbitrarySeqGraph\rangle|$.

Let constant $$\begin{aligned}
\label{Eq:Sigma}
\sigma=\max_{q\in Q}|U_{(q)}|\end{aligned}$$ wherein sets $$U_{(q)}=\{s\ |\ ((q,s),(q',s',m))\in\Delta\}$$ and $\Delta$ is the transition relation of machine $M\langle NP\rangle$.

The estimations of the time and space complexities of the constructed Turing machines are shown in figures \[Fig:TSCompl\].

  -- -- --
        
        
        
        
        
        
  -- -- --

The following is taken into account in the estimations of the time and space complexities of the machine:

1.  [the count $n\_count$ of the nodes in graph $TArbitrarySeqGraph$ is ${\mathsf{O}}(t(n)^2\log(t(n)))$ because the number of steps that are needed to compute the next computation step is ${\mathsf{O}}(\log(t(n)))$;]{}

2.  [the count $n\_count_1$ of the nodes, that correspond to the computation steps of Turing machine $M\langle NP\rangle$, in graph $TArbitrarySeqGraph$ is ${\mathsf{O}}(t(n)^2)$;]{}

3.  [the count $e\_count$ of the edges in graph $TArbitrarySeqGraph$ is ${\mathsf{O}}(\sigma\cdot n\_count)$;]{}

4.  [value $k=|TConsistPairSet|$ is ${\mathsf{O}}((n\_count_1)^2)$;]{}

5.  [the count $r$ of the paths in graph $ArbitrarySeqGraph$ is $2^{{\mathsf{O}}\left(\sigma\cdot n\_count\right)}$;]{}

6.  [the matrix of the equations of linear program [[**TCPELP**]{}]{} is $${\mathsf{O}}\left(n\_count\cdot k)\times{\mathsf{O}}(e\_count\cdot k\right)$$ matrix;]{}

7.  [the count of the equations in linear program [[**TCPELP**]{}]{} is ${\mathsf{O}}\left(n\_count\cdot k\right)$;]{}

8.  [the count $v\_count$ of the variables in linear program [[**TCPELP**]{}]{} is ${\mathsf{O}}\left(e\_count\cdot k\right)$;]{}

9.  [the length $L$ of the input of linear program [[**TCPELP**]{}]{} is ${\mathsf{O}}\left(n\_count\cdot e\_count\cdot k^2\right)$;]{}

10. [Karmarkas’s algorithm performs ${\mathsf{O}}(v\_count^{3.5}L)$ operations on ${\mathsf{O}}(L)$ digits numbers wherein $v\_count$ is the number of the variables and $L$ is the length of the input of linear program [[**TCPELP**]{}]{};]{}

11. [${\mathsf{O}}\left(p^2 q\right)$ steps of multi-tape Turing machine are needed to get the elements of an array with $p$ elements wherein the length of each element is ${\mathsf{O}}(q)$;]{}

12. [the number of the iterations in the loops of algorithm $$DetermineIfExistsTConsistSeq$$ is ${\mathsf{O}}\left(t(n)^2\right)$;]{}

13. [the number of the iterations in the main loop of machine $M\langle\exists AcceptingPath\rangle$ is ${\mathsf{O}}\left(t(n)\right)$;]{}

14. [deep-first traversal (if it is used), which is a recursive algorithm, of tree $TArbitrarySeqTree$ can be simulated on a deterministic multi-tape Turing machine using a stack of depth ${\mathsf{O}}(t(n))$;]{}

here $t(n)$ is an upper bound of the time complexity of machine $M\langle NP\rangle$.

Main results
============

In this section, machine $M\langle\exists AcceptingPath\rangle$ is used to introduce the main results. Constant $\sigma$ (in propositions \[Prop:EveryLangNDisD\]) is defined by equation .

Main theorem
------------

If $M$ is a deterministic multi-tape Turing machine that computes a function $f(x)$ and works in time $t(n)$, then one can construct a deterministic single-tape Turing machine $M'$ that computes the same function and works in time ${\mathsf{O}}\left(t(n)^2\right)$ [@DK00]; therefore, the following proposition holds.

\[Prop:EveryLangNDisD\] Every language in a finite alphabet that is decidable by a non-deterministic single-tape Turing machine in time $t(n)$ is also decidable by a deterministic single-tape Turing machine in time [${\mathsf{O}}\left(\sigma^{24} t(n)^{208}\right)$]{}, wherein $t(n)$ is an upper bound of the time complexity of machine $M\langle NP\rangle$, and $\sigma$ is a constant depending on relation $\Delta$ of machine $M\langle NP\rangle$.

If $t(n)$ is a polynomial, then machine $M\langle\exists AcceptingPath\rangle$ works in polynomial time in $n$ ($n=|x|$ wherein $x$ is the input of the machine); therefore, the following main theorem holds.

\[Thr:PeqNP\] $$\begin{aligned}
{\text{\bf P}}={\text{\bf NP}}.\end{aligned}$$

Some consequences
-----------------

From the construction of machine $M\langle\exists AcceptingPath\rangle$, one can conclude that the following proposition holds.

Every language in a finite alphabet that is decidable by a non-deterministic single-tape Turing machine in space $s(n)$ is also decidable by a deterministic single-tape Turing machine in time $2^{{\mathsf{O}}(s(n))}$.

This result is also obtained by simulating non-deterministic computations on a deterministic Turing machine [@DK00].

In addition, proposition \[Prop:EveryLangNDisD\] is consistent with the fact that if [[**P**]{}]{}$\,=\,$[[**NP**]{}]{} then the following equality holds: [[**EXPTIME**]{}]{}$\,=\,$[[**NEXPTIME**]{}]{} [@Papa94; @DK00].

The possibility of finding an accepting computation path, using machine $M\langle\exists AcceptingPath\rangle$, is consistent with the fact that [[**FP**]{}]{}$\,=\,$[[**FNP**]{}]{} iff [[**P**]{}]{}$\,=\,$[[**NP**]{}]{} [@Papa94].

One of the most important consequences of theorem \[Thr:PeqNP\] is that [[**P**]{}]{}$\,=\,$[[**PH**]{}]{}.

Computer program to verify the results
======================================

[[**C\#**]{}]{} application to verify the results is developed using [[**MS Visual Studio Express 2012**]{}]{} and [[**Wolfram Mathematica 8.0**]{}]{}; the application is available on the Internet at [@App].

The solution contains some examples for languages $$\begin{aligned}
&L_1=\{ w1\ |\ w\in \{0,1\}^*\}\ \text{and}\\
&L_2=\{ x11z\ |\ x,z\in \{0,1\}^*\} \cup \{ x00z\ |\ x,z\in \{0,1\}^*\};\end{aligned}$$ the application verifies that machine $M\langle \exists AcceptingPath\rangle$ works correctly for these languages for small inputs. Other languages can be easily added: Just construct single-tape non-deterministic Turing machines for them.

Language $L_1$ is decidable by deterministic Turing machine; this language is used just to verify that machine $M\langle \exists AcceptingPath\rangle$ works correctly for deterministic Turing machines (polynomial time deterministic Turing machine is used in the construction of machine $M\langle \exists AcceptingPath\rangle$).

Despite of the fact that languages $L_2$ is also decidable by deterministic Turing machine, polynomial time non-deterministic Turing machine is used in the construction of machine $M\langle \exists AcceptingPath\rangle$ for language $L_2$ just to verify that machine $M\langle \exists AcceptingPath\rangle$ works correctly for non-deterministic Turing machines.

It would be nice to verify the results for a [[**NP**]{}]{}-complete problem, for example, problem [[**3-CNF-SAT**]{}]{}, or problem [[**Shortest Common Supersequence**]{}]{} [@GJ79]. But it is not possible for now because of too high (but still polynomial) time complexity of machine $M\langle \exists AcceptingPath\rangle$. The application requires too much computer resources, both time and space; computer resources are mainly consumed by linear program solver.

For example, it takes about 1 Gb of RAM when the length of an accepting computation path is greater than 15. In that case, linear program with about 4000 variables and 4000 equations is solved; it takes about 1 Gb of RAM to solve such linear programs by the linear program solver.

Conclusion
==========

This paper presents the program of deterministic multi-tape Turing machine $M\langle\exists AcceptingPath\rangle$ that determines in polynomial time if there exists an accepting computation path of polynomial time non-deterministic single-tape Turing machine $M\langle NP\rangle$ that decides a language $A$ over a finite alphabet (machine $M\langle \exists AcceptingPath\rangle$ is different for each machine $M\langle NP\rangle$). As a result, the equality of classes [[**P**]{}]{} and [[**NP**]{}]{} is proved.

The computations presented in this paper are ‘not ordinary’ computations in the sense that the tape-inconsistent sequences of the computation steps are used to determine if there exists an accepting computation path of machine $M\langle NP\rangle$. The author of this paper proposes denoting these computations by one of the following:

1.  [using-complement computations;]{}

2.  [superfluous computations.]{}

But these computations is ordinary in the sense that the computations are preformed by Turing machines; the computations presented in the present paper are not quantum computations, for example, or other kind of computations which uses non-standard concepts.

The concept suggested in the present paper can be applied in some a way not only for Turing machine programs but also for computer programs written on imperative programming languages like Pascal or C\#. But it is not clear for now if the algorithms proposed in the present paper can be used in practice to implement non-deterministic algorithms using deterministic imperative programs because of too high computational complexity of linear program solvers for now.

[9]{} D.Du, K.Ko *Theory of Computational Complexity.* John Wiley and Sons, 2000. p.491. S.A.Cook *“The complexity of theorem proving procedures”* in Proc. of the Third Annual ACM Symposium on Theory of Computing, 1971. pp.151–158. L.A.Levin *“Universal search problems”* in Problemy Peredaci Informacii 9, pp.115–116, 1973. Translated in problems of Information Transmission 9, pp.265–266. S.A.Cook *“The P versus NP Problem”.*\
Internet: [www.claymath.org/millennium/P\_vs\_NP/pvsnp.pdf](www.claymath.org/millennium/P_vs_NP/pvsnp.pdf) M.F.Sipser *“The history and status of the P versus NP question”* in STOC ’92 Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing, 1992. pp.603-618. S.A.Cook *“The importance of the P versus NP question”* in Journal of the ACM (JACM), Vol.50, Issue 1, 2003. pp.27-29. A.Wigderson *P, NP and Mathematics – A computational complexity perspective.* In: Proceedings of the ICM 2006, Madrid, Vol.I, pp.665-712. EMS Publishing House, Zurich, 2007. L.Fortnow *“The status of the P versus NP problem”* in Communications of the ACM, Vol.52, Issue 9, 2009. pp.78-86. R.J.Lipton *The [[**P**]{}]{}$\,=\,$[[**NP**]{}]{} Question and Godel’s Lost Letter.* Springer, 2010. p.253. Cornell University Library *“Computational Complexity”.*\
Internet: <http://arxiv.org/list/cs.CC/recent> G.J.Woeginger *“The P-versus-NP Page”.*\
Internet: <http://www.win.tue.nl/~gwoegi/P-versus-NP.htm> M.R.Garey, D.S.Johnson *Computers and Intractability: A Guide to the Theory of [[**NP**]{}]{}-Completeness.* Freeman, 1979. p.338. A.Schrijver *Combinatorial Optimization [(3 volumes)]{}.* Springer, 2003. p.1800. L.G.Khachiyan *“Polynomial algorithms in linear programming”* in Zh. Vychisl. Mat. Mat. Fiz., 20:1, 1980. pp.51–68. N.Karmarkar *“A new polynomial time algorithm for linear programming”* in Combinatorica, Vol.4, nr.4, 1984. pp.373–395. S.Arora, B.Barak *Computational Complexity: A Modern Approach.* Cambridge University Press, 2009. p.594. C.H.Papadimitriou *Computational Complexity.* White Plains: Addison-Wesley, 1994. p.523. O.Goldreich *Computational Complexity: A Conceptual Perspective.* Cambridge University Press, 2008. p.632. R.M.Karp *“Reducibility among combinatorial problems”* in Complexity of Computer Computations. New York: Plenum, 1972. pp.85–103. F.Nielson, H.R.Nielson, C.Hankin *Principles of Program Analysis.* Springer (2nd printing), 2005. p.452. S.A.Cook *“The Complexity of Theorem Proving Procedures”* in Proceedings of the third annual ACM Symposium on Theory of Computing, 1971. pp.151–158. S.Even, A.Itai, A.Shamir *“On the complexity of timetable and multicommodity flow problems”* in SIAM Journal on Computing (SIAM) 5 (4), 1976. pp.691–703. T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein *Introduction to Algorithms, Third Edition.* The MIT Press, 2009. p.1312. A.Schrijver *Theory of Linear and Integer Programming.* John Wiley and Sons, 1998. p.484. S.V.Yakhontov *[[**C\#**]{}]{} program to verify the [[**P**]{}]{}=[[**NP**]{}]{} results.* Internet:\
<https://sites.google.com/site/sergeyvyakhontov/home/peqnp-paper-status/>
