What are the consequences of saying a non-deterministic Turing Machine can solve NP in polynomial time?

Question

these days I have been studying about NP problems, computational complexity and theory. I believe I have finally grasped the concepts of Turing Machine, but I have a couple of doubts.

I can accept that a non-deterministic turing machine has several options of what to do for a given state and symbol being read and that it will always pick the best option, as stated by wikipedia

How does the NTM "know" which of these actions it should take? There are two ways of looking at it. One is to say that the machine is the "luckiest possible guesser"; it always picks the transition which eventually leads to an accepting state, if there is such a transition. The other is to imagine that the machine "branches" into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path" that it follows, an NTM has a "computation tree". If any branch of the tree halts with an "accept" condition, we say that the NTM accepts the input.

What I can not understand is, since this is an imaginary machine, what do we gain from saying that it can solve NP problems in polynomial time? I mean, I could also theorize of a magical machine that solves NP problems in O(1), what do I gain from that if it may never exist?

Thanks in advance.

Noam

That's an old idea. It's called an Oracle Machine. – Tenterhook

Answer 1

A non-deterministic Turing machine is a tricky concept to grasp. Try some other viewpoints:

1. Instead of running a magical Turing machine that is the luckiest possible guesser, run an even more magical meta-machine that sets up an infinite number of randomly guessing independent Turing machines in parallel universes. Every possible sequence of guesses is made in some universe. If in at least one of the universes the machine halts and accepts the input, that's enough: the problem instance is accepted by the meta-machine that set up these parallel universes. If in all universes the machine rejects or fails to halt, the meta-machine rejects the instance.

2. Instead of any kind of guessing or branching, think of one person trying to convince another person that the instance should be accepted. The first person provides the set of choices to be made by the non-deterministic Turing machine, and the second person checks whether the machine accepts the input with those choices. If it does, the second person is convinced; if it does not, the first person has failed (which may be either because the instance cannot be accepted with any sequence of choices, or because the first person chose a poor sequence of choices).

3. Forget Turing machines. A problem is in NP if it can be described by a formula in existential second-order logic. That is, you take plain-vanilla propositional logic, allow any quantifiers over propositional variables, and allow tacking at the beginning existential quantifiers over sets, relations, and functions. For example, graph three-colorability can be described by a formula that starts with existential quantification over colors (sets of nodes):

   ∃ R ∃ G ∃ B

   Every node must be colored:

   ∃ R ∃ G ∃ B (∀ x (R(x) ∨ G(x) ∨ B(x)))

   and no two adjacent nodes may have the same color – call the edge relation E:

   ∃ R ∃ G ∃ B (∀ x (R(x) ∨ G(x) ∨ B(x))) ∧ (∀ x,y ¬ (E(x,y) ∧ ((R(x) ∧ R(y)) ∨ (G(x) ∧ G(y)) ∨ (B(x) ∧ B(y)))))

   The existential quantification over second-order variables is like a non-deterministic Turing machine making perfect guesses. If you want to convince someone that a formula ∃ X (...) is true, you can start by giving the value of X. That polynomial-time NTMs and these formulas not just "like" but actually equivalent is Fagin's theorem, which started the field of descriptive complexity: complexity classes characterized not by Turing machines but by classes of logical formulas.

You also said

I could also theorize of a magical machine that solves NP problems in O(1)

Yes, you can. These are called oracle machines (no relation to the DBMS) and they have yielded interesting results in complexity theory. For example, the Baker–Gill–Solovay theorem states that there are oracles A and B such that for Turing machines that have access to A, P=NP, but for Turing machines that have access to B, P≠NP. (A is a very powerful oracle that makes non-determinism irrelevant; the definition of B is a bit complicated and involves a diagonalization trick.) This is a kind of a meta-result: any proof solving the P vs NP question must be sensitive enough to the definition of a Turing machine that it fails when you add some kinds of oracles.

---

The value of non-deterministic Turing machines is that they offer a comparatively simple, computational characterization of the complexity class NP (and others): instead of computation trees or second-order logical formulas, you can think of an almost-ordinary computer that has been (comparatively) slightly modified so that it can make perfect guesses.

Captain

+1. I've never heard of that oracle theorem -- it sounds awesome. – Holst

Answer 2

What you gain from that is that you can prove that a problem is in NP by proving that it can be solved by an NTM in polynomial time.

In other words you can use NTMs to find out whether a given problem is in NP or not.

Mattern

Can you please elaborate on that? How can I prove something like that using an NTM? – Noam

@Clash: You construct an NTM which solves the problem. Then you prove that it is correct and that it runs in polynomial time. – Mattern

Can you post an example, a link to study such thing? I'm completely lost on how to do that. I'm not used to think non-deterministically. Thanks! – Noam

@Clash: for example, you can find if a graph has a tricolouring by non-determistically guessing it. For |V| first rounds, you assign colours to vertices, and then check if your colouring is correct. See NP-complete problems for more examples. – Bummer

Answer 3

By definition, NP stands for nondeterministic polynomial time as can be looked up in Wikipedia.

An incarnation of a nondeterministic Turing machine that randomly chooses and examines (or assembles) the next potential solution will solve an NP problem in polynomial time with some probability (it would solve the problem in poly time with absolute certainty if it were the "luckiest possible guesser").

Therefore, saying that an NTM can solve a problem in polynomial time effectively means that that problem is in NP. This again is equivalent to the definition of the NP class of problems.

Incorporable

Thanks for clarifying, but you still haven't answered my question... if such lucky guesses doesn't exist, why is this any useful... it's like saying, hey, if I could know the results of the lottery before it happens I'd be rich. NTM must be useful for something else. This is what I can't understand. – Noam

It is hoped that quantum computers are (with some limitations) able to simultaneously test all potential solution paths and therefore behave like the luckiest possible guesser NTM. Quantum computers compute with qubits, where any set of qubits represents a set of all possible combinations of the same number of conventional bits (superposition). (Peter) Shor's algorithm for factoring numbers / cracking RSA encryption exploits this. – Incorporable

The hard part with quantum computers though is protecing the superposition from decoherence (where the qubits turn to conventional bits by means of physical interaction with the world) and extracting the correct solution from it in the end by decoherence. – Incorporable

Answer 4

I think your answer is in your question. In other words, given a problem you can prove that it is an NP problem if you can find an NTM that solves it.

NP problems are a special class of problems, and the NTM is just a tool to check if the given problem belongs to the class or not.

Note that the NTM is not a specific machine - it is a whole class of machines with well defined rules of what they can and cannot do. In order to use "magical" machines, you need to define them, and show which complexity class of problems they correspond to.

See http://en.wikipedia.org/wiki/Computational_complexity_theory#Complexity_classes for more info.

Cork

If NP can also be defined as the problems that can be VERIFIED in polytime with TM, why would I need a NTM, that doesn't even exist? Thanks – Noam

verifying a solution in polytime with a TM is equivalent to solving in polytime with an NTM. en.wikipedia.org/wiki/NP_(complexity)#Verifier-based_definition" (see Machine-definition) – Cork

Sometimes it is just easier to come up with the NTM than the TM, but in order to prove a problem is NP both solutions are valid. – Cork

Answer 5

From Hebrew Wikipedia - "NTM is mainly a tool for thinking, and it's impossible to actualy implement such machine". You can replace the term "NTM" with "Algorithm that at every step tries all possible steps" or "Algorithm that at every step chooses the best possible next step".. And I think you understand the rest. NTM is here only to help us visualize such algorithm. You can see here how it's supposed to help you visualize (at Pascal Cuoq's answer).

Aufmann

"Algorithm that at every step can select from a number of possible steps". Anything can 'select' anything. NTM is just a lucky guesser that can pick the correct path at each step. – Brabazon

@OTZ: You can also think about it as if it's trying all possibilities (click the link I gave). Both definition are equal. But you were right, the original wording wasn't good. Changed it. – Aufmann

Answer 6

What we gain is that if we have the magical power to guess the correct step, which will always turn out to be correct, we can solve NPC problems in POLYTIME. Of course, we can't always "guess" the correct step. So it's imaginary. But just as imaginary numbers are applicable to real world problems, consequences can be theoretically useful.

One positive aspect of morphing the original problems this way is that we can tackle them from different angles. In a theoretical domain, it is a good thing because we have (1) more approaches we can take (thus more papers) and (2) more tools we can use if they can be phrased in other fields.

Brabazon

I use imaginary numbers all the time at electrical engineering, they have real use and advantages. On the other hand I can't see any advantage of saying that is something can be solved magically in polytime. The thing I'm looking is exactly these real world problems that can be helped by a NTM. Thanks @DanJ, he is talking about NTM, therefore it is solved in polytime. – Noam

@Noam We can't apply NTM to any real world problems as it is impossible to create one in the first place. For one advantage, read the second paragraph I've just added. – Brabazon

@Cork it's NPC. what's up with your attitude. – Brabazon

Imaginary numbers also do not exist, still we use them in many situations. I'm interested in those cases where an NTM is useful for anything. I think it's finally getting into my head that NTM is useful to prove that a certain problem is NP, whereas using a deterministic TM to prove such thing would be harder, what I need now is an example of how can I prove such thing with an NTM. Can you think of any or do you know any link to such thing? Thanks! – Noam