I have problems to imagine a non-deterministic Turingmachine. Let's make an example: There is the problem of a Vertexcover. Let $G=(V,E)$ be an undirected graph and $k\geq 0$. The question is whether there is a vertexcover $C$ of size $|C|\leq k$. My book says that this problem is in $NP$, because a Turingmachine could just guess a subset $C\subset V$ with $|C|\leq k$ and check in polynomial time, whether we have a vertex cover. If it guesses the set $C$ randomly, it could be possible that it does not work. So it just guesses another $C$. My question: Will it guess every possible pair $(C,k)$? In other words, is it possible that the machine is stuck in an infinite loop by always guessing the same?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
A non-deterministic machine finds the solution "by magic": whenever there is a decision to be taken, it immediately takes the right one so that the search for a solution essentially amounts to the verification of the solution. There is no randomness involved and the machine is run once on the given problem.
-
$\begingroup$ So if there is a solution to the problem, the nondet TM will right away take the path to it. But if not? What happens then? $\endgroup$ Commented Mar 22, 2023 at 18:52
-
$\begingroup$ The machine will somehow report "no solution". $\endgroup$– user16034Commented Mar 22, 2023 at 19:06