jewish_scientist wrote:"Can a non-deterministic Turning machine solve a puzzle such that a function describing how long it will take the machine to solve the puzzle is not a polynomial?" Iff the answer is yes, then P =/= NP.
Is this correct?
Here are a two ways of looking at this definition, because no, not really. For example, you are only talking about the runtime of the nondeterministic machine. Or... "what puzzle" are you talking about? There are certainly puzzles that NTMs can solve in polytime, so it can't be "there exists a puzzle such that...". But there are also certainly puzzles that NTMs can not
solve in polytime, and provably so; so it can't be "for all puzzles" either. (The solution to this is that it's for all, but you compare the runtime of the best NTM to the best DTM.)
The first definition is the following. Take some puzzle, and consider the fastest (asymptotically) non-deterministic and
the fastest deterministic turning machines that can solve that puzzle; let f
be the function that describes the runtime of the NTM and g
describe the runtime of the DTM. P = NP if, for all puzzles, either both f
are polynomial or neither
is. P != NP if there's some puzzle that can be solved in polytime by an NTM but cannot be solved in polytime by a DTM.
The second definition is the following. Let P be the set of puzzles that can be solved by a DTM in polytime. Let NP be the set of puzzles that can be solved by a NTM in polytime. Well, P = NP just does set comparison on those sets. (Formally, a "puzzle" is a function that produces a Boolean output.)
The two are basically the same (because S = T
for sets is defined to be "x ∈ S iff x ∈ T
for all possible elements x
"), but they're two sides of the same coin so maybe one will "stick" better.
One other way of looking at it is the following. I think
this is right, but I'm tired and I've got a nagging feeling I'm getting something wrong.
There are some things you can do to a Turing machine that increase its expressiveness. For example, you can have TM definitions where the tape is infinite in both directions or in just one direction. Or you can have a TM definition that allows multiple tapes. In these cases, it is possible to take a TM that uses that extra expressiveness and convert it into a TM that doesn't (e.g. convert a multi-tape TM to a single-tape TM) such that the runtime of the resulting TM doesn't increase "too much." For this discussion, "too much" means that if the original TM always runs in polytime, then the resulting TM will always run in polytime as well.
Consider nondeterminism as something that increases the expressiveness of a TM. Nondeterministic TMs can
be converted to DTMs, but with a catch: it's not known how to do it efficiently. The only known conversions will increase the runtime of the original TM exponentially. If P = NP, then we're missing something, and there is
a way to do that conversion and preserve the polynomial runtime of the original. If P != NP, then we're not, and that conversion isn't possible to do in general.