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

+3 A:

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.

sepp2k 2010-09-14 22:15:13

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

Clash 2010-09-14 22:17:43

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

sepp2k 2010-09-14 22:20:05

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!

Clash 2010-09-14 22:53:21

@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.

sdcvvc 2010-09-15 15:55:19

Thanks sdwc, will take a look!

Clash 2010-09-15 16:40:16

A:

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).

Oren A 2010-09-14 22:24:06

"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.

OTZ 2010-09-14 22:29:13

@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.

Oren A 2010-09-14 22:31:20

+1 A:

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.

Archimedix 2010-09-14 22:34:41

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.

Clash 2010-09-14 23:39:36

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.

Archimedix 2010-09-15 13:56:59

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.

Archimedix 2010-09-15 14:06:31

A:

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.

OTZ 2010-09-14 22:39:26

np problems are verified in polytime, not solved.

DanJ 2010-09-14 22:55:23

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.

Clash 2010-09-14 22:56:35

@Clash 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.

OTZ 2010-09-14 22:59:10

@DanJ it's NPC. what's up with your attitude.

OTZ 2010-09-14 23:01:04

@OTZ 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!

Clash 2010-09-14 23:52:08

A:

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.

DanJ 2010-09-14 22:53:59

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

Clash 2010-09-14 23:49:33

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

DanJ 2010-09-15 18:41:53

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.

DanJ 2010-09-15 18:44:15

+3 A:

Jouni K. Seppänen 2010-10-03 11:06:53

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

Edmund 2010-10-03 11:41:55

ansaurus

tags:

views:

answers:

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

related questions