0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Mar 22, 2023 at 18:52
  • $\begingroup$ The machine will somehow report "no solution". $\endgroup$
    – user16034
    Mar 22, 2023 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.