In this paper we consider the next more powerful restricted type of Turing machine, which cannot be handled by the existing lower bound arguments: Turing machines with one work tape and a two-way input tape. We show that one can simulate a deterministic Turing machine of this type with time bound $O(n^3 )$ by $\Sigma _2 $-Turing machine of the same type with time bound $O(n^2 \cdot \log ^2 n)$. This implies the new separation result $\Sigma _2 {\operatorname{TIME}}_1 (n) \nsubseteq {\operatorname{DTIME}}_1 ({{n^{{3 / 2}} } / {\log ^6 n}})$. Further, we improve Kannan’s separation result ${\operatorname{NTIME}}(n) \nsubseteq {\operatorname{DTIME}}_1 (n^{1.104} )$ to ${\operatorname{NTIME}}(n) \nsubseteq {\operatorname{DTIME}}_1 (n^{1.22} )$. Finally we show that with Turing machines of the considered type that use $2k$ alternations, the achieved speed-up increases and for large k approximates $t^{{1 / 2}} (n)$. In view of the close relationship between spacebounded Turing machines and time-bounded Turing machines with unboundedly many alternations, this refinement provides a link between our speed-up result and the well-known space-compression result for offline 1-tape Turing machines.

We consider the problem of computing the shortest path between two points in two- or three-dimensional space bounded by polyhedral surfaces. In the 2-D case the problem is easily solved in time $O(n^2 \log n)$. In the general 3-D case the problem is quite hard to solve, and is not even discrete; we present a doubly-exponential procedure for solving the discrete subproblem of determining the sequence of boundary edges through which the shortest path passes. Finally we consider a favorable special case of the 3-D shortest path problem, namely that of finding the shortest path between two points along the surface of a convex polyhedron, and solve it in time $O(n^3 \log n)$.

We consider the problem of computing the shortest path between two points in two- or three-dimensional space bounded by polyhedral surfaces. In the 2-D case the problem is easily solved in time O(n2 log n).In the general 3-D case the problem is quite hard to solve, and is not even discrete; we present a doubly-exponential procedure for solving the discrete subproblem of determining the sequence of boundary edges through which the shortest path passes. The main result of this paper involves a favorable special case of the 3-D shortest path problem, namely that of finding the shortest path between two points along the surface of a convex polyhedron. We analyze this problem and solve it in time O(n3 log n).