This seminar by mark-t took place on 12th October 2008 17:00 UTC, in #mathematics channel of

The timestamps displayed in the IRC text are UTC+1.
Any explanation or errors regarding this seminar should be recorded in the discussion page.

Seminar Edit

18:36:28 ChanServ changed the topic of #mathematics to: SEMINAR IN PROGRESS.  If you want to
                 ask a question, say ! and wait to be called

18:00:25 ~vixey: oh did I miss it
18:00:41 mark-t: nope, should be starting nowish
18:00:50 ~vixey: oh that's perfect!
18:02:58 mark-t: well, I'm starting now, with or without a topic change
18:04:02 mark-t: so, last time I gave a very brief introduction to turing machines
                 and gave a somewhat precise statement of the P vs. NP problem
18:04:17 mark-t: but I don't feel like I really got across why anybody cares about
                 this problem
18:05:04 mark-t: it might seem like turing machines are just some toy to be played
                 with, and whether or not you can design fast ones to recognize
                 certain languages may seem a rather trivial thing to worry about
18:05:46 mark-t: so, I'd like to spend a few minutes discussing how powerful turing
                 machines are and why they're relevant to anything
18:06:08 mark-t: let's go back to my previous example:


18:06:44 mark-t: as you'll recall, this turing machine recognizes strings that have
                 the same number of 'a's as 'b's
18:07:06 mark-t: it works in four steps:
18:07:15 mark-t: 1) find the first 'a' or 'b' in the string
18:07:31 mark-t: 2) if you found an 'a' in the string, cross it off, and find the next 'b'
18:07:50 mark-t: 3) if you found a 'b' in part 1), cross it off, and find the next 'a'
18:08:23 mark-t: 4) if you found a 'b' in 2) or an 'a' in 3), cross it off and rewind to
                    the beginning of the string; repeat
18:09:19 mark-t: now, one thing you'll notice is that each of these steps is tied to a state
                 in the machine
18:10:15 mark-t: so, while DFAs use states to record everything it knows about the string so
                 far, turing machines use states to keep track of what step they're in in an
                 algorithm, and they use the tape for memory
18:10:33 mark-t: in this way, turing machines are much more like CPUs than DFAs
18:11:35 mark-t: and that's how turing machines tend to be designed, as well; you think of
                 steps to do a process, and you make a state for each step, instead of
                 thinking about which strings are fundamentally different to the language and
                 making them go to different states
18:12:30 mark-t: so, this is all summed up pretty well by the church-turing thesis, which
                 states that any language that can be recognized by an effective algorithm
                 can be recognized by a turing machine
18:13:04 mark-t: you can get more precise about that, but you should basically just have the
                 idea that turing machines can compute anything you or I or your computer
                 could compute
18:14:13 mark-t: and therefore, it should be no surprise that turing machines have equivalent
                 power to non-deterministic turing machines; since we can trace things
                 through and figure out if a non-deterministic turing machine accepts a given
                 string, so can an ordinary turing machine
18:14:35 mark-t: ok, so that brings us to the question of P vs. NP
18:15:19 mark-t: one thing that strikes me about this problem is: ok, so you give the turing
                 machine a string of length n; what on earth is it doing for an exponential
                 amount of time? why is there anything that takes that long?
18:16:12 mark-t: well, it turns out that you can define languages with arbitrarily large time
                 complexity; I'd like to show you how to create one
18:16:52 mark-t: for this example, I'll make one whose time complexity is at least O(2^n),
                 but it will be quite obvious how to get the general case
18:17:10 mark-t: so, our alphabet for this example will just be {a}
18:17:55 mark-t: it should be pretty clear that the number of turing machines is countable;
                 we need to get an ordered list of these and name them M_0, M_1, M_2, etc.
18:19:03 mark-t: so, to build this language, we start by checking the empty string,
                 then "a", then "aa", then a^3, and so on
18:19:31 mark-t: at each step, we may mark a machine as canceled, which means that it cannot
                 accept the language we're building
18:20:31 mark-t: so, here's how we check a^n; find the first uncanceled machine M_j, only
                 checking machines up to M_n, that halts in less than 2^n steps when reading
                 the string a^n
18:20:55 mark-t: if there isn't such a machine, don't add a^n to the language
18:21:46 mark-t: if there is such a machine, mark it as canceled; if it accepted the string,
                 don't add a^n to the language; if it rejected the string, add a^n to the
18:22:02 mark-t: and that's it
18:22:16 ~vixey: ?
18:22:19 mark-t: yes?
18:22:36 ~vixey: Do you have a picture of that machine?
18:22:51 mark-t: no; it would be quite a mess to construct, but this is all possible
18:23:39 mark-t: we can clearly associate a string to any turing machine; in order to make
                 the list M_0, M_1, etc., we just have to generate them in order
18:24:01 mark-t: which could be something as inefficient as just generating every string in
                 order and seeing if it's a valid turing machine
18:24:24 mark-t: we can clearly run any turing machine for 2^n steps and see if it accepts a
                 given string
18:24:52 mark-t: and since we're only checking finitely many turing machines for each n, all
                 of this will eventually finish
18:25:47 mark-t: I'll be avoiding the design of actual turing machines today, speaking more
                 about what they can and can't do instead
18:26:10 mark-t: ok, so, let's show why this language has a time complexity at least O(2^n)
18:26:47 mark-t: first of all, we know there's some machine that can accept this language,
                 since it can do all the steps I just described
18:27:19 mark-t: next, any machine that accepts this language must not be canceled in this
18:27:42 mark-t: so, suppose we have a turing machine that accepts this language, and it's
                 given by M_k
18:28:15 mark-t: by design, the only way that it could avoid being canceled is by taking 2^n
                 steps or longer for every n >= k
18:28:46 mark-t: and therefore, for any machine that accepts this language, the time
                 complexity is at least O(2^n)
18:29:35 mark-t: so, I hope it's abundantly clear how to make a language with arbitrarily
                 large time complexity in this way, though it isn't necessarily clear what
                 the machine is doing for all that time
18:29:55 mark-t: I can't necessarily help you with that  8)
18:30:29 mark-t: ok, back to P vs. NP
18:31:25 mark-t: one approach to this problem is looking at certain languages, which are
                 called NP-complete
18:32:19 mark-t: a language in NP is called NP-complete if every language in NP can be reduced
                 to it in polynomial time
18:32:50 mark-t: reduced means that you can transform the question about a string in one
                 language to a question about a string in this language
18:33:46 mark-t: for example, if one language recognizes primes and another recognizes squares
                 of primes, you reduce the former to the latter by squaring the input and
                 checking if it's a square of a prime
18:34:40 mark-t: working in non-negative integers, of course
18:35:10 mark-t: first of all, it's not clear that an NP-complete language should exist; I'll
                 get to that in a minute
18:35:59 mark-t: but if a language is NP-complete, then we know two things: if that language
                 is in P, then P = NP; if that language is not in P, then P < NP
18:36:29 mark-t: of course, if we find any language in NP that isn't in P, then P < NP
18:37:06 mark-t: however, since that would imply that all of the NP-complete languages are
                 not in P, the NP-complete languages are the obvious ones to look at
18:37:40 mark-t: you can think of an NP-complete language as being one of the hardest
                 languages to recognize in NP
18:38:02 mark-t: now, back to the question of whether there even exists a language that is
18:38:51 mark-t: here's the first example; the theorem that shows it's NP-complete is called
                 Cook's Theorem
18:39:06 mark-t: the problem is the boolean satisfiability problem
18:39:30 mark-t: so, suppose you have a bunch of boolean variables; that is, each one takes a
                 value of either true or false
18:40:33 mark-t: and you have a bunch of expressions in these variables, which consist of
                 some of these variables and/or their complements "or"ed together
18:41:01 mark-t: for example, "~x1 v x2 v x3" (not-x1 or x2 or x3) would be such an expression
18:41:53 mark-t: the boolean satisfiability problem asks, given a set of these expressions,
                 whether there some assignment to the variables that makes all of the
                 expressions true
18:42:00 mark-t: is
18:43:22 mark-t: the proof of Cook's Theorem is rather extensive, so I won't go through it,
                 but the main idea is that it takes the computation of a turing machine and
                 expresses each step as a set of boolean expressions that all have to be true
18:44:11 mark-t: and then, if there's a solution to the set of boolean expressions, it means
                 the turing machine will accept the language; if not, then it won't
18:44:52 mark-t: it shouldn't be too surprising that you can do this, as our computers express
                 just about everything in terms of whether or not a given set of bits is true
                 or false
18:45:27 mark-t: once you have one NP-complete language, finding others is much less work
18:45:55 mark-t: now, all we have to do is show that a given language is in NP and that some
                 NP-complete language reduces to it in polynomial time
18:46:52 mark-t: since every language in NP will reduce to the NP-complete language in
                 polynomial time, every language in NP could then be reduced to this language
                 by reducing to the NP-complete language first
18:47:11 mark-t: oh, right, I forgot to mention why the boolean satisfiability problem (SAT)
                 is in NP
18:48:13 mark-t: as you know, non-deterministic machines can do many computations in parallel;
                 the implication is that they can generate all of the possible solutions and
                 check each one in parallel
18:48:48 mark-t: and the time to generate a solution and check if it satisfies all of the
                 boolean expressions is clearly polynomial in the length of the set of
18:50:42 mark-t: this is a hallmark of NP-complete problems; there's generally some signature
                 that can be computed to show when the answer is yes, and it can be checked
                 in polynomial time
18:51:06 mark-t: the non-deterministic machine can just generate all of the possible
                 signatures and check them in parallel
18:51:38 mark-t: the naive deterministic machine has to do them in series, which is why it's
                 not clear whether or not they can do it in polynomial time
18:52:04 mark-t: ok, so here's another problem that is NP-complete
18:52:09 mark-t: this one is called 3SAT
18:52:33 mark-t: 3SAT is similar to SAT, except the expressions are required to have at most
                 3 variables each
18:53:12 mark-t: 3SAT is clearly in NP, since it can be checked by the same non-deterministic
                 turing machine that checks SAT
18:53:30 mark-t: to show that 3SAT is NP-complete, we'll reduce SAT to it
18:54:21 mark-t: that is, we need to show that, given an expression from SAT with n variables,
                 we can reduce it to a set of expressions with 3 variables that all have to
                 be true
18:54:59 mark-t: so, let's say our expression was ~x1 v x2 v x3 v ~x4 v ...
18:55:59 mark-t: the idea is that we can replace the first two variables in the expression
                 with a new variable, say y, and add an additional expression that makes
                 sure y is only true when (~x1 v x2) was true
18:56:31 mark-t: by this process, we reduce the length of the original expression by 1 and
                 add one new expression
18:56:52 mark-t: if the original expression had n variables, we'll have to do this n-3 times
18:57:31 mark-t: so, for the additional expression, we want to force y to be false
                 unless ~x1 v x2 is true
18:57:47 mark-t: that is, ~y v ~x1 v x2 must be true
18:58:19 mark-t: 'cause if ~x1 v x2 is false, then we have to make y false in order to
                 satisfy this expression
18:59:04 mark-t: and that's basically it; there's some analysis to show that this isn't going
                 to create a set of expressions that's exponential in the length of the
                 original set, but that's not hard to see
18:59:51 mark-t: you can't possibly be adding more than n expressions of fixed length when
                 given a set of expressions containing n total variables
19:00:19 mark-t: therefore, we've reduced SAT to 3SAT; any SAT problem can be expressed as a
                 3SAT problem
19:01:36 mark-t: 3SAT is kind of a funny case; it's harder to reduce other problems to it,
                 but it's easier to reduce 3SAT to other problems, so 3SAT is generally
                 better than SAT for showing that another language is NP-complete
19:02:04 mark-t: there are lots of other NP-complete languages, but I don't have time to go
                 into them
19:02:57 mark-t: some famous examples are the hamiltonian path problem, which is a special
                 case of the traveling salesman problem, the subset sum problem, the vertex
                 cover problem, and so on
19:03:26 mark-t: and, unfortunately, these problems are important in computer science, so we
                 would really like to have fast algorithms to solve them
19:03:46 mark-t: that's why the P vs. NP problem is so important
19:03:56 mark-t: so, that's all I have planned for today
19:03:59 mark-t: thanks for reading
19:04:20 ~vixey: thank you! very interesting againa
19:04:22 tcoppi: :D thanks, nice talk
19:04:41 jamesstanley: so np-hard problems are problems that need to be brute forced?
19:05:03 mark-t: NP-hard problems are problems that any NP problem reduces to
19:05:07 jamesstanley: ok
19:05:12 mark-t: an NP-hard problem is NP-complete if it's in NP
19:05:23 ~vixey: I sort of want to see one of these turing machines
19:05:26 mark-t: it might be worse than NP, too
19:05:53 mark-t: the book I mentioned last time, "Languages and Machines" by Sudkamp does
                 construct one for SAT
19:05:58 mark-t: I think
19:06:08 mark-t: maybe it was for the hamiltonian path problem
19:06:16 mark-t: it does one of these NP-complete problems
19:06:45 mark-t: but yes, generally the problem with np-hard problems is that we don't know
                 a significantly better way than brute force
19:07:35 ~vixey: I bet you make a simple langauge and compile it into these turing machine
                 state transition things
19:08:37 mark-t: there are lots of constructs that have been shown to be equivalent in power
                 to turing machines
19:08:54 mark-t: one of them is called a while-language, I think, which is somewhat more like
                 ordinary programming languages
19:10:36 ~vixey: what's happening next time?
19:10:59 mark-t: not me  8)