3
The idea is quite simple. We are going to simulate running $M_f$ (the machine for $f$) on $g(x)$. Let $m = |g(x)|$, and note that $\log m = O(\log n)$. In order to do that, we keep track of the location of the input tape head of $M_f$ (this takes $O(\log m)$ space), as well as the contents of the work tapes (which also takes $O(\log m)$ space). Whenever $M_f$...
3
Using the proof of the Cook–Levin theorem, for every input $x$ you can construct in polynomial time a SAT instance $\phi(r,z)$ which encodes "$M$ accepts when run on input $x$ and randomness $r$". Here $r$ is a vector of $m = \mathit{poly}(n)$ bits, representing the random bits of $M$, and $z$ is an auxiliary vector, with the following property: in any ...
3
Is it possible to make a machine that when it encounters a non-deterministic step it takes an arbitrary one? Yes easily.
Will this machine be able to solve NP problems in P? No because it will most likely pick the wrong path through the execution.
Similarly for outputting a number there is no way to force the machine to match the required path needed to ...
3
As Wikipedia says, there are two conditions for strongly polynomial time algorithms:
the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
the space used by the algorithm is bounded by a polynomial in the size of the input.
I will simply call these two ...
3
Cook up some encoding of Turing machines so that if $n$ codes a machine, $2 n$ codes "the same" (perhaps use binary numbers ending in 1 as starting points, and 0s at the end are disregarded, thus making that odd $n$ and $n \cdot 2^k$ represent the same machine). Then use that e.g. $\operatorname{HALT}(M)$ (does $M$ halt if started on an empty tape?) isn't ...
2
A classic example of an uncomputable function is The Busy Beaver Problem: For each N, consider all N-state Turing Machines over the alphabet { [blank], 1 }; over all of those machines which always halt when started on a blank tape, find one which leaves the maximum possible number of 1's on the tape once it has halted; then f(N) is that number of 1's.
2
I will assume that $g(G, v)$ computes a valid vertex cover, so it can never report a more optimal solution, and does so in polynomial time.
We know that vertex cover is NP-hard to approximate within a factor below 1.36: http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf. Since $g(G, v)$ reports a solution at most 5 more than optimal, ...
2
In general, it is impossible to even determine if it will ever halt. And if it halts, determining the number of steps is also impossible. Check out the busy beaver game for details.
There are general techniques that work in a large proportion of cases of practical interest, for a start check out the reference question here. But there have been complete ...
2
Maybe the Turing Machine Linear Speed Up Theorem will answer your doubt (https://en.wikipedia.org/wiki/Linear_speedup_theorem)
Counter-intuitively or maybe intuitively, this states that given a Turing Machine which does something in say $n$ steps there are Turing Machines which can solve the same problem in $n/k$ steps for any constant $k$ independent of $n$...
1
For $R(x,y)$, $x$ is where $M$ is a TM, $y$ is the accepting configuration of $M$. Is this a polynomial-time relation?
Yes that is the right idea. Except $y$ should be a sequence of configurations that starts in the initial configuration and ends in the accepting configuration.
To see why this works, we have to consider the running time of the TM that ...
1
First we assume for the $S_3$ is decidable and let TM $R$ be the decider for $S_3$. With $R$, we can test whether $M$ writes symbol $``3"$ on the third cell of its tape at some point. If $R$ indicates that $M$ doesn't write $``3"$ on the third cell, reject because $\big \langle M,3 \big \rangle \notin A_{TM}$. If $R$ indicates $M$ writes symbol $``3"$ on the ...
1
Both HP and MP are decision problems, namely sets of instances that you can think of as descriptive strings. For example,
HP is a collection of pairs $M, x$ where $M$ is the description of a Turing Machine (think of a listing) and $x$ is an input to that machine. An instance is such a pair and a pair is in the set HP if the machine described by $M$ ...
1
Search for Bellare and Goldwasser "The Complexity of Decision vs. Search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119, or Bellare's class note on the matter.
1
Another way to do it: Take any non-computable function $g(n)$, then the function defined as:
$\begin{equation*}
f(2^k (2 n + 1)) = g(n)
\end{equation*}$
for all $k \ge 0$ satisfies your conditions.
1
The direction of reduction that you are asking for is a bit strange. Typically, we reduce from $A_{TM}$, in order to show undecidability.
Perhaps you meant to ask about the other direction?
At any rate, in answer to your question: your attempt was actually quite close, it just needs a bit of modification. Here's how you can proceed:
Given $M_1,M_2$ as ...
1
The final m-config for the second configuration is an "e".
Only top voted, non community-wiki answers of a minimum length are eligible
