This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to
do Cryptography: a set of questions compiled to give PhD
candidates a sense of what they should know by the end of their first
year. We continue the Complexity Theory section with NP...
Well,
an NDTM is a Turing Machine for which the transition function can have
multiple values for the same tape value/state pair (meaning it is not
technically a function any more, so the correct thing would be to call
it a transition relation). Thus evaluation of an NDTM on any particular
input can be thought of as a tree, branching at each point the
transition function provides more than one possible value. Now, an NDTM
evaluates all of these possible branches at once, and accepts if at
least one of these computations halts in the accept state. This definition generalizes from language membership to decision to computational problems in the same way as P did in last weeks blog.
Last week, Ryan introduced us to complexity classes, and in particular to P:
- P is the class of languages decidable in polynomial time by a deterministic Turing machine.
This week, we introduce another complexity class:
- NP is the class of languages decidable in polynomial time by a nondeterministic Turing machine.
What is a Nondeterministic Turing Machine (NDTM)?
Well,
an NDTM is a Turing Machine for which the transition function can have
multiple values for the same tape value/state pair (meaning it is not
technically a function any more, so the correct thing would be to call
it a transition relation). Thus evaluation of an NDTM on any particular
input can be thought of as a tree, branching at each point the
transition function provides more than one possible value. Now, an NDTM
evaluates all of these possible branches at once, and accepts if at
least one of these computations halts in the accept state. This definition generalizes from language membership to decision to computational problems in the same way as P did in last weeks blog.Some Examples of NP problems
We
begin with an easy example: path finding. Given a directed graph (on n
vertices) is there a path from vertex A to vertex B. How do we know this
is in NP? Well, there is an NDTM that solves it, which basically works
by simply trying every route by branching each time there is a junction.
If one of these branches (ie one of the trial routes) reaches B, then
that branch terminates in the accept state. Any branch that does not
reach B within n steps (ie after traversing n edges) terminates in the
reject state. Since any path will involve at most n-1 edges, any valid
route will be detected, and so this machine correctly decides whether
the path exists.
One of the key examples of an NP problem is the satisfiability problem:
For example, the expression $(A \land B) \lor (A \land \lnot B)$ is satisfiable,
with one valid assignment being A=B=True. Note that in it's standard
form, SAT is a decision problem: it suffices to decide whether such an
assignment exists, we don't have to find it.One of the key examples of an NP problem is the satisfiability problem:
- SAT: Given an expression in n boolean variables, is there an assignment of the variables such that the expression evaluates to True?
Ok, so there are problems in NP. What is interesting about it?
Firstly, we see that P⊆NP
since a DTM is an NDTM that just happens not to ever branch (in fact,
our first example can actually be solved by a DTM and so is within P). So, the real question is what sort of things can we do in NP that we couldn't do in P? Well, this is the root of the P$\overset{?}{=}$NP millenium problem, which is a major open problem. There are certainly problems that we have found that are known to be in NP that we do not know to be in P, but perhaps future research will show that these are also in P.
Lots
of interesting cryptographic systems (particularly in the public key
setting) are secure based on the assumption that a computational problem
is "hard", which generally means "at least as hard as any problem in
NP". That is, many schemes are based on problems which we think are
difficult to solve, and that if you can create an algorithm that solves
them you could also use this algorithm to solve lots of other problems
that we currently believe to be difficult.
The Cook-Levin theorem provides an interesting result in this direction: No problem in NP is any harder than SAT. What his means is that if I had an oracle (basically an algorithm that I can see the input/output of but none of the workings) that solved SAT, by asking it to solve cleverly constructed queries I could use it to solve any other NP problem. This made SAT the first example of an NP-complete problem. So, to show that a problem X is at least as hard as solving an NP problem (it is NP-hard), it suffices to show that if I could solve X, I could use it to solve SAT.
The Cook-Levin theorem provides an interesting result in this direction: No problem in NP is any harder than SAT. What his means is that if I had an oracle (basically an algorithm that I can see the input/output of but none of the workings) that solved SAT, by asking it to solve cleverly constructed queries I could use it to solve any other NP problem. This made SAT the first example of an NP-complete problem. So, to show that a problem X is at least as hard as solving an NP problem (it is NP-hard), it suffices to show that if I could solve X, I could use it to solve SAT.
No comments:
Post a Comment