PROFESSOR: All right. So Lecture 7 was

about many things– universal foldings by box

pleating, maze folding, and then lots of

NP hardness stuff. So we’re going to go through

things in that order. I thought I’d start by showing

some old history of box pleating, where it comes from. The first design is by this guy

Raymond McLain, 1967, design called the Mooser’s train. And you can see all the creases

are horizontal, vertical, and diagonal, 45 degrees. This is the original

handwritten thing, and this is apparently before

the time of origami books, for the most part. So people would

just photocopy this, and hand it around, just

kind distribute it out through the origami community. And kind of spawned a

revolution origami design, because it was the

first model to make sort of a very complicated

multi-object piece out of one piece of paper. Happened to be a

rectangle of paper, but a pretty cool design . And it really got

people thinking about. And the basic, original

principal in box pleating was to make boxes, and then find

ways to attach them together. And it’s fairly

powerful and believed to be universal by

origamists for a long time. And we proved it with

that cube gadget. Now, the designs that come

out of the cube gadget are not especially efficient. I’ve got some ways to

optimize it, as you saw, but at least it proves

everything is possible that you could

make out of cubes, you can make out

of box pleating. Another kind of

influential design is this black

force cuckoo clock. For a long time, one of the most

complicated origamis out there. It was designed by

Robert Lang in the ’80s, and there’s a few of

them in existence. It has lot of detail– it

has a clock, that’s correct twice a day, and it’s he

modeled it after a real cuckoo clock he saw in

the Black Forest. It’s got a zillion

creases, especially in this long rectangle of paper. And there’s diagrams for it

in Origami Design Secrets, if you want to make your own. And it’s also based on

this box pleating idea, and sort of in the early days

of the tree theory, and so on. So really, before that kicked

off, box pleating was around. And people still do

basic box pleating, although now there’s

the fusion of the tree method with box pleating. There’s a lot of designs

based on that, because they’re easy to fold from

angular perspective, easy to find where the

creases are, anyway, that’s box pleating. So next, we go on to– I

think it’s an open problem. Yeah, this is a

cool open problem. For some reason, never

thought about it. I’m sure briefly thought about

it, but never worked on it. In the same way we get

universal hinge patterns, box pleating can make any poly

cube, what if you want to make, out of the simple cube gadget,

can we design an analogous cube gadget for

tetrahedra, octahedra, might be nice, regular octahedra

tile space, out of something like a triangular grid,

maybe with 30 degree lines. That’s a natural

question– open. Maybe we’ll work on it sometime,

but I think it’d be neat. You just need a nice

gadget, and then we know how to compose them by

induction just like in lecture seven. So it could be a

fun thing to attack. Next, we go to maze folding. So I thought I’d

show– we’ve seen this maze fold– the 6.849. So this is folded

by Jenny and Eli based on the algorithm that

you saw, and you might play with it on your

problem set three. Design your own maze. You can click any

pattern you want. Make whatever letters you want,

or any other cool orthogonal pattern. Marty and I have made a

bunch of different print designs based around this idea

of taking not just the crease pattern you get for

folding– here we’re folding the word yes

in three dimensions– but we’ve shaded the original

piece of paper in this pattern. So that it looks like nothing

on here, but when you fold it, the shading comes

together to spell no. So it’s kind of ambiguity, or

the shadow of the yes is no, and so on. And Jenny and Eli folded

that as well, and here it is. The first folding. But our idea is not

necessarily to fold them. I mean, it’s cool that

they can be folded. That’s neat

conceptually, but we also like to design ones that

really should not be folded. Next one here is

science and art, so you fold the science

in three dimensions and the art is in the

background lurking there. I imagine this will

never be folded. It’d be rather painful. Here’s another very

complicated one. Here we’re playing around with

putting little shaded regions in these squares. These are just the

squares that end up mapping to the flat

parts over here. And so you get–

we took an image and spliced it up into

thousands of pieces. So you get– this is a

photograph of Martin Gardner, who died a couple

years ago sadly. We never met him,

but he was the father of recreational mathematics

among other things. Also magician–

lots of cool things. So this is in tribute to him. And this is our latest

design in this spirit. We’re trying to be a

little more artistic and just be about the crease

pattern, not necessarily the folding. So the 3-D thing that this

folds into is not shown here, and in theory all these

lines go off to infinity. But this spells the word glass. We made it when we were at

the Pilchuck Glass School this summer. And it’s now on t-shirts of many

glass blowers around the world. How many of them know

exactly what it folds into, I don’t know. But that’s pretty cool. So we were working

on glass folding, so that seemed like a

natural thing to do. So that is maze folding

and see some designs. How you can use it

for cool things. The next topic is

NP-hardness, and that will be what we spend

most of today on. And so, first kind

of general question is what does it all mean? What does NP-hardness

really tell you? Can you give me like a

specific instance that’s hard, and– this is more for people

who haven’t seen MP-hardness before– the answer is no. NP-hardness is kind of a

conceptual, philosophical thing. No specific problem

is ever NP-hard. It’s all about whole families

of problems being hard. And really it’s about

measuring the growth of problem complexity with problem size. So in this case, it’s

how much running time do you need to

solve your problem as a function of

the problem size. And we’re interested in whether

that grows only polynomially or it grows exponentially,

and NP-hardness probably implies exponential growth. A nice example of this is chess. So eight-by-eight

chess– people have spent many years trying to

solve it and do it perfectly, and to be the best player. But from a theoretical,

computer science perspective, chess in its original

form, is trivial because it just has a

constant number of states. You could just enumerate

them all in constant time. You know who wins in

chess– probably white. But it’s not very satisfying,

but the more interesting thing to say is to study

chess as it grows, and the natural way to make it

grow is with an n-by-n board. So with an n-by-n

board, if I give you an arrangement of

chess pieces and I want to know who wins,

that you can prove is something even stronger than

NP-hardness called X-hardness. So there you can actually

prove you need exponential time to solve n-by-n chess. And that gives you a sense

the chess really is hard. There’s not going to be a good

algorithm that magically will solve it for eight-by-eight,

because in general as board size increases, you know it

has to grow exponentially, and probably eight-by-eight

is big enough. That there’s no good

algorithm to do it. You can’t prove that

there’s no good algorithm to do eight-by-eight,

but you can prove there’s no good

algorithms to do n-by-n. So that’s the limitation of

theoretical computer science and of NP-hardness. So you take any

particular crease pattern. You want to know

whether it folds flat. You might be able to do

that by exhaustive search and exponential

time might be OK, but you know that as the

crease patterns get big, you’re totally screwed. So, next question about

hardness is can we do it with a little

less hand waving? So in a little bit

more detail, because I covered a lot of proofs. So I’m going to

look at two of them. The simple full hardness–

which is from partition– and the crease pattern

flat foldability which is from not all equal

SAT– 3SAT– and I’ll give some more details. So let’s start by going

through this proof. Remember, in general with

an NP-hardness reduction, we want to take some

known hard problem and convert it into our

problem, because that proves that our problem is at least

as hard as the original one. So in this case, the known

hard problem is I give you n integers– a1, a2, up to an. And I want to know, can I

split them into two groups so that the two

groups have equal sum? And here we’re mapping that into

the simple fold problem, which was given a crease

pattern can you fold it. Can you follow all the

creases flat by simple folds? We’re mapping it

into these lengths– these lengths are the AIs

between the different legs of the staircase. And then there’s

this extra stuff. This is a super long

length– length l– and this is a doubly

super long length– 2l. And then there’s this

frame, which has height 2l, and this part is aligned

right at the midway. And so the idea was if there’s

a partition– if there’s a partition of the AIs

into two groups– call them Group A and Group

B– then I’m going to fold some of the creases. The ones between any two

guys of different groups. Because folding here corresponds

to switching directions. So whenever I fold, I’m kind of

switching which group I’m in, and then Group A will

be all the up directions and Group B will be all

the down directions. So maybe both of these

guys are in Group B so they both go down, and this

is a Group A guy, so we go up, and then down, and then up. And if we get them– A and

B to be balanced– then we’ll end up right

where we started. So we’ll end up right at

the middle point here. And, in that case, there’s

these two more folds– this vertical fold and

that vertical fold. And then if you– sorry. Yeah, I don’t have

it drawn here. When you do one more fold here,

this will fall into the frame, and if you got this to stay–

if you got this point basically to be aligned with

here, then going up L, and then back down to L will

not collide with this box. It just barely fits,

and so you fold that in. Then you fold this vertical

line and you fold it back out. So the goal was just to

get these two folds made. Once they’re made and

it’s back out here, you can finish all folds

that you didn’t fold before. And what we’re checking here

is that during all this motion, you don’t get collision

because simple folds are not allowed to collide

during the motion. So if this, for example, went

too far down or too far up and it collided with

the frame, then you wouldn’t be able to make the

second vertical fold here because you’d have to

bring the frame with you, and the frame’s not

supposed to move. So in particular,

there’s this question. Seems like we’re not

making all the folds, and that’s because I

didn’t say the last part. After you fold it in

here and avoid collision, you fold it back out with the

second of these two folds. Then you can finish

all the folds. Indeed the goal is

to fold everything, but in order to avoid

collision, when I fold this, this thing has to be nice and

compact and fit within this 2L boundary. Then it goes through. So what we really

need to show though at the top level is

given any set of AIs, we can convert it into an

equivalent simple fold problem. There’s actually two things we

need to check for equivalence. We need to check that

if there’s a partition, then there’s a way to fold it. We also need to check

the reverse, which is if there’s a way to fold

it, then there’s a partition. But both of these kind of

follow from this argument. In order to– when

we make this fold, this guy’s got to– or

whichever of these two is first. They’re kind of equivalent. If we collide, we won’t be

able to finish the folding. That’s the claim. You might have done all

the folds over here, but they’ll be the

second of these two, and so when you do the first,

you’ll either get stuck or you’ll be able to proceed. If you were able to

proceed, you can read off from the ups and downs here

what the partition was. So you can convert in either

direction using this reduction. Any more questions about

the simple folds one? So, of course, one of the easier

proofs, the crease pattern flatfold ability is definitely

on the more complicated side, and this was the

overview of the proof. Basically there were lots

of little local gadgets. There’s the wire,

which communicates truthiness or falsity

as we like to say. Or things like– the

main gadget is the one at the top and not

all equal clause, which forces among the

three wires coming in. They can’t all have

the same value. So there could be

two true, one false. Or two false, one true. But not all true

and not all false. And then we needed

some auxiliary gadgets for turning, duplicating,

and crossing over. Those were fairly

straightforward. The heart is a wire, and

a not all equal clause. And so the idea was we were

given a formula– in this case, it’s a bunch of triples,

and each of the triples should be not all equal. And there’s like n

variables– there’s a lot of different clauses

on those variables. A lot of not all equal

constraints on those clauses. We want to represent that

by the flatfold ability of the crease pattern. So we basically make

all the variables off the left edge

of the paper here. We make lots of copies

of them by zigzagging, and then we make lots of clauses

at the top– only drawn two up there– and then in our input

we’re given a bunch of triples of variables that should

belong to a common clause, and we just route these

signals to go to that clause. And then the clauses constrain

the values of those variables to be not all equal in

the appropriate triples. And the splitters

down here enforce all the different copies of

that variable to be the same. And so any flat

folding will require these guys are consistently

assigned one truth value throughout

the construction, and those clauses will

force not all equal things to be seen in pairs. So if there’s a flat

folding of this, you can read off on the

mountain valley assignment here which one based

on whether it’s left valley, right mountain,

or left mountain, right valley. You can read of what

the truth assignment is that satisfies all the clauses. That was one direction

from flat foldability to satisfiability of the

not all equal triples in the reverse direction. If there’s a not all equal

assignment of triples, you need to verify that this

thing actually does fold flat. I didn’t detail

that, but basically to do that, you have to prove

that each of the gadgets works exactly as desired. So you could really fold it

flat if these have equal value, for example, and this

has a negated value. You could actually always

fold the not all equal cause when it’s satisfied. And then once you know that

each of these gadgets– because the gadgets are

very small– once you know that each of them

folds correctly, and they have a sort

of comparable interface because these things are

just extending through, you could basically paste

glue together all of those folded states. So as long as you

verify the gadgets work, the whole thing

will work provided there is a satisfying

assignment. So that’s– yeah, question? AUDIENCE: Can you actually

go in the other direction properly in the same cell? Can you map any flat

foldability [INAUDIBLE]? PROFESSOR: OK, can you

map any flat foldability of a crease pattern

problem to SAT? That doesn’t follow

from this proof, but I think it should be true. Uh, let’s see– I think so. So if I give you

a crease pattern, I want to know

whether it folds flat. As mentioned in lecture,

you can determine where all the facets lie in 2D. And challenges the

stacking order, which implies the mountain

valley assignment. So I think you could

make a variable in a SAT problem for this piece–

this little polygon lives in the stacking level. You have to figure out how many

levels you need, but at most 10 of them, I guess. And then write down

the constraints between different polygons

if there are no crossings. There’s a paper

by Jacques Justin that does that explicitly. So that should give you a way to

reduce to SAT, which gives you an algorithm– an exponential

time algorithm to solve it. In general, I’m pretty

sure this problem is in NP, which implies there’s

at least an algorithm for it. But I think in particular,

you can reduce it to SAT. So that’s a good question. So pretty much

every problem we’ll talk about at least with

origami has a finite algorithm to solve it, but it’s a very

slow algorithm in general. Of course, there’s a lot of

good SAT solvers out there, and I don’t know if people

have actually tried to do that. I know there are some– there’s

a software called ORIPA, which in Japan some

versions try to find a valid folding– a

valid folded state by some kind of careful,

exhaustive search. I don’t think they use

SAT solvers though. You might get more mileage

out of SAT solvers. Other questions

about this proof? There’s one explicit question

about the reflector gadget. This probably worth talking

about because these arrows are maybe not so

obvious what they mean. So the question is what

is true and what is false. It’s kind of philosophy,

but in this case these arrows are explicitly

drawn on this diagram. If you look closely, there’s an

arrow this way, then this way, then this way. And that’s defining what we mean

by the orientation of a wire, and then if it’s a valley

on the left relative to the arrow, that’s true. If it’s mountain on the

left relative to the arrow, that’s false. And that’s why this

is drawn this way assuming I got it right. Here it’s valley on the

left relative to the arrow. Here it’s mountain on the

left relative to the arrow. So notice these are pointing

in different directions. So that can get a

little confusing, but it’s kind of what

we want in that proof because we really want to route

that thing in this direction. We don’t care about

what things look like relative to

the center here. Because the center– the

gadget we are looking at keeps changing. So we want to route

this as a single wire. And this one I

already talked about. You need to prove

both directions– that flat foldability implies

not all equal satisfiability, and the reverse. OK, we move on. So now we get to

some new material. So I mentioned in the

lecture that there are two hardness proofs. The one we’ve been talking

about is given a crease pattern, does it fold flat? That’s strongly NP-hard. And the other is if I

give you something– I might even tell you

it’s flat foldable. That’s kind of not too relevant. But I give you

mountains and valleys, and I want to know–

I want to find a valid folded

state of that, or I want to decide whether

the mountain valley pattern is valid. These are strongly NP-hard hard,

and this is a different proof. It uses completely

different gadgets. So I thought I’d show you

some of those gadgets. Sort of the key ones. So the first part

is the wire, and I think I made one of these. Maybe I didn’t. No wire. Well, this is the end

of a wire– er, no, that’s not the end of a wire. Here’s an end of a wire. So the idea here is we’ve

got a fixed mountain valley pattern now because that’s

no longer free for the folder to choose. And you’ve got

two tabs, and they could stack one

way or the other. In this case, they

can stacked like this, or they can stack like that. So I’ve got a

choice in stacking. That changes the folded state. That’s the choice that the

folder is going to make, but in either case the mountain

valley assignment is the same. So that’s how we’re going to

communicate true and false, and I haven’t

provided orientation. Should have drawn

an arrow there. Next gadget is this tab

gadget, and this is just a tool for building

weird shapes, and it’s kind of similar

to some of the things you’ve seen in the

checkerboard folding. So our crease pattern looks

like this, and fold it flat. And there’s two ways to fold it. Actually, a few

different folded states. But in particular,

there’s a state like this where there’s this

individually manipulatable tab, but there’s no crease here. So it can’t go backwards. The crease is in here. So it’s got a fall

down like that. OK, so what this reduction

does is, ahead of time basically, force a

lot of these foldings. And so we start

with a square paper. We end up with a smaller square

paper with tabs sticking out in various directions

of various places. So this is much messier

and it’d be harder to draw the whole diagram of

what your crease pattern looks like, but in theory

you can do this. That’s also kind of

like the box pleading method where you just

make a cube ahead of time, and it’s like you had

a square originally. There just happens to

be a cube sitting here, and then you do other folding. And the angles in this

crease pattern– these are not 45 degrees. They’re at a bit

of a weird angle to basically force

this to happen first. It can’t interact with

any of the other gadgets that I show you. Because you’ve got to get rid of

those angles in the beginning. Then, the main gadget here

is the not all equal clause, and that’s what I

have folded here. So it’s a little crazy,

but basically you’ve got three pleats– three of

these double pleats coming together. These guys could stack– this

one on top, this one on top. Now we’re the same

for all three of them, and then you’ve got this little

twist like thing in the center, and it’s really

hard to draw what the folded state looks like. This is what it looks

like within shadow pattern with transparency. Here’s the real thing. And also, there’s

these yellow tabs attached at very

specific locations. And this is a little

hard to imagine. I encourage you to fold

one of these in order to really see what’s going on. But as I said before, you’ve

got– each of these guys can be independently stacked

one way or the other. There’s that one or this one

can stack this way or that way for all three, but we want

to forbid the case where they’re all stacked

the same way. And the arrows here are all

pointing towards the gadget. So we want to forbid

the case when they’re all– when it’s

rotationally symmetric. Gadget is rotationally

symmetric, but if you choose the layer

order rotationally symmetric, you’re in trouble. So let me make it

rotationally symmetric. That would be like this. So when it’s

rotationally symmetric, you see– basically

all the panels you see– there’s three panels. This one, this

one, and this one. Each of them has a

tab sticking out, and basically these tabs have

to also be cyclically ordered, but it’s not possible–

this is hard to do. It’s like this. You see they’re kind

of colliding here. Because if you look at each

of the tabs in projection, it collides with where

the tab is attached. So you basically– if you went–

so someone has to be the lowest tab, and that tab will intersect

the other two tabs actually where that tab is attached. So it’ll penetrate

and you can see they’re not very

happy to stack here. But if I change the

layer order in any way, our lowest tab is actually

happy to go behind other layers, and then you can just stack

them, and they barely fit. So it’s a little tricky to get

all the details here to work, but I think this particular

geometry– and the reason I drew this in this exact way

is to make sure yeah, everything works. You do not penetrate here,

which would be a problem. You do not penetrate

this crease, which would be a problem. So the tab just fits in

between here and here, but it does cross. If you look at this tab,

it’s attached along this edge as drawn up there. And this tab here will penetrate

this part of that edge, and it will penetrate this

part of this edge which is where this tab is attached. So they cause trouble in

this cyclic situation, but when it’s a cyclic

like in this picture, you can put that

bottom tab way down here and avoid any collision. Then you can basically

break the cyclic condition, and you get to stack them

in some linear order. So it’s a little hard to

see without physically manipulating it. Feel free to come and

play with that after. That’s their proof. Now there’s also splitters, and

turn gadgets, and crossovers, but I’ll leave it at that. Those are more similar. This is the heart of what’s

going on in this proof. So it’s a completely

separate proof from the one that we saw before. Any questions about that? All right– AUDIENCE: Here. PROFESSOR: Yeah? AUDIENCE: I don’t understand

why the tabs fold. PROFESSOR: How do the tabs fold? AUDIENCE: No, why do we need

tabs if everything folds? PROFESSOR: So the tabs

are being used as a device to build gadgets. So the tabs serve no

purpose by themselves. But this gadget involves

first folding three tabs here, which are actually

pointing– they’re pointing in that

direction, I believe. Then you add this crease

pattern afterwards. So originally there

are tabs here, which means there’s a

bunch of creases here. After you fold them, then you

lay on this crease pattern. So if you unfolded it, you

get some much more complicated crease pattern. Which is when I made that,

I just taped the tabs on. But in reality, first you fold

the tabs so they exist there, then you fold this on top. So the fold crease pattern

would be quite complicated. It’s going to have

tabs here, tabs here, tabs there, and then this

reflected a few times. And so then when you

fold it– the fold gadget is this thing with the tabs. The tabs are just

like a stepping stone toward making this gadget. The other gadgets use more tabs. Obvious open problem here is

to make a simpler reduction. Shouldn’t have to

be this complicated, and I’ve heard Tom Hall talk

about different approaches for making simpler

NP-hardness proofs, but we’re not there yet. Other questions? AUDIENCE: So these proofs

don’t imply anything about the [INAUDIBLE]? They can all be very

easily [INAUDIBLE]. PROFESSOR: So this proof

implies these kinds of tessellation style crease

patterns are hard to fold, which implies that

in general crease patterns are hard to fold. But you could look at some

other specific pattern. For example, it’s

the next topic. You could look at

map folding where you have horizontal

and vertical creases in a rectangular sheet of paper. Maybe each of these squares

is– or each of these cells is a unit square, let’s say. And I give you a mountain

valley assignment on that. Some of these are mountains. Some of them are valleys. Whatever. And I want to know

does this fold flat? That we don’t know

the complexity of. Could be solvable by

polynomial time algorithm. Could be NP-hard. And this is actually mentioned

in lecture two notes, but not actually orally. And so I wanted to

get back to this. This is from lecture two notes. 2D map folding, Jack

Edmonds poses this problem, can you characterize flat

foldable mountain valley pattern. Is there an algorithm

or is it NP-hard? And even the 2-by-n

problem was open when I wrote these

notes in 2010, but it has since been solved. So I thought I’d tell you a

little bit about that solution. So yeah, there can be special

cases of crease patterns that are easy to solve. We just know in

general they are hard. So 2-by-n is this

kind of picture. So this is what I call

2, counting cells. This is based on a class

project in this class from two years ago by

Eric Lew and Tom Morgan, but the paper got

finished this year. So it’s based on a

series of reductions. On the one hand, we’re going to

start with something called– OK, so we have map

holding on the left. We’re going to

convert map folding into a different presentation,

which is NEWS labeling. We’re going to convert that

into something called a top edge view. We’re going to convert

that into a ray diagram. And the last part, which I

won’t talk too much about, is we convert that into

something called a hidden tree problem. Each of these steps is

fairly straightforward, but there are obviously

a lot of them. But in the end, you get a

polynomial time algorithm to solve this, which implies

you get a polynomial time algorithm to solve this. And I’ll talk mostly

about these reductions. It’s the same idea

in NP-hardness. We use reductions from a

hard problem to our problem. In this case, we’re

doing the reverse. We’re reducing our problem

to an easier problem, so that by the end we

get something that’s so easy we know how to solve it. The reductions are useful

both for positive results and negative results. So let me show you

visually some– oh, before we get

to the proof, I wanted to mention this

puzzle which you probably folded in problem set one. It’s a map folding problem. It’s a 3-by-3 map,

and so we didn’t have any good algorithms

to solve them. So we used a not

so good algorithm– namely exhaustive enumeration. We enumerated all possible

folded states of a 3-by-3 map. We drew them out graphically. There’s a scroll bar here,

so you don’t see them all. But we put them in

a giant– I forget, there’s 1,000

folded states or so, so it’s like 100-by–

whatever– 10 array. And for each of

them– so here’s where you’re designing your pattern. So you could make holes. You could put in patterns. This is sort of an early design

where it would spell MIT. The hole would show

the I on another side, so it’s equivalent to

the puzzle you solve. And this is what

the top looks like. This is what the

bottom looks like. So you can hover over these

and change the letters that appeared, and then

it would show you what every single

state would look like, and it would color it in yellow

if one side looked like MIT, and it would color it in red

if both sides look like MIT. And the point was

to verify there was exactly one solution

for that puzzle. And so we kept– we

would fold things to make it a tricky fold. Then we put into the

software and label things accordingly, then

put into the software and see is there unique folding? And then we could add in

extra misleading clues here, and see did they accidentally

make an extra solution? So we could add in

extra stuff to pack in. As much irrelevant stuff as we

could, and still make it unique so it’s more challenging. That’s a nice use of exponential

algorithms to design puzzles. All right, but

back to this proof. So I have here a much

simpler map than this one. This is what we

call the NEW map. N-E-W. So the labeling

here is very simple. If you look at this crease

pattern, by [INAUDIBLE], there’s got to be three of one

type and one of the other type. So just label each vertex

by which way is unique. So from here, the

North direction is the uniquely label– it’s the

mountain among three valleys. And then this vertex–

the East label– is the mountain

among three valleys, and then the next one is the

West label among three valleys. Of course it doesn’t

have to be like that. It could, for

example, you can have three mountains at a vertex,

but then the label of this guy’s going to be W. It’s going

to be the one that’s unique among the other three. So if you fold this

map, it looks like this. I have one here, but it’s

a little hard to see. We’ve got lots of back

and forth on the top edge. Some orienting it so that

the– we’ve got 2 by n maps. So there’s two

critical features. There’s the center line. I’ll call that the

spine of the map. There’s the top side

and the bottom side. When you fold

that– this is just a sequence of simple folds. You see at this last fold, the

top side and the bottom side come together, and the

spine is– stays together. So when I orient it like

this as in the picture, the top side is where originally

the top and the bottom of the map all come to here

because of that spine fold, and the spine folds

are all down here. You can’t see them

here, but there’s you can see them at

the bottom there. There’s some kind of

connections on the bottom, but there’s this nice relatively

one-dimensional picture up here. So we’re going to draw that. This is the top edge view. Got clipped a little

bit, but there’s one more segment at the top. So that is just this. See it? Now there’s also

these blue lines. The blue lines correspond to

what’s going on at the bottom from the spine. Because if you think

about it, you’ve got the– in a

2-by-n map– you’ve got the top panels and these

edges making the top edge. And you’ve also got the

bottom panels and these edges making the bottom edge. They come in pairs. These guys are paired up. These guys are paired up,

and so on down the line because they are

joined by a spine edge. Those spine edges

correspond to the things on the bottom of the

folding, and they need to not cross each other. And that’s what’s illustrated

by the blue connections. So the very top edge is paired

with the very bottom edge. These two– this panel

here and the back panel here– are connected

on the bottom. And that– I’m sorry,

that’s not true. This one is paired

with this one. The top one is paired

with the second one. So it’s actually these two

are connected on the bottom. That’s this little connection

here, and then these guys– this wraps around everything. That’s that connection. But what you can’t see

it in this folding– because it’s hidden inside–

is that within this connection on the bottom, there’s this

connection on the bottom. And within that one,

there’s this connection. Now this is OK. Might look like they’re crossing

because they’re overlapping. But as long as they

are nested– as long as you don’t start from

inside here and go to outside. That would be a crossing. You start inside,

you should end inside like in all these pictures. If you start outside,

you should end outside. So that’s why– these guys

are disjoint, so that’s OK. This is nested in

that, so it’s OK. Kind of like

balance parentheses. And so that’s what it makes. A top valid top edge view. What’s nice about this is it’s

a one-dimensional diagram. What’s not nice is it has all

these crossings because there’s the blue stuff on top

of the black stuff. So it’s a little

hard to find– we’re trying to find a

valid folding state. We’re trying to

find one of these. We’re not restricting ourselves

to simple folds here yet. Simple map folding we already

solved in lecture two. So this is all– I should’ve

said non-simple folds. That’s what makes

it hard, and that’s what’s still open

for 3-by-n maps if you don’t know how to do it. But for 2-by-n maps,

we’ve made two steps here. We have another view,

which is the ray diagram, and this is really

specific to 2-by-n. And it lets us reduce

to a tree problem. So before we get there,

let’s talk in general about the top edge view. You can actually convert from

the North, East, West, South labeling to a top edge

view in the following way. Whenever– and you can kind

of see what’s going on. So first we have an n. So we’ve got these

two guys, which are just paired

together happily. That’s the beginning of the map. Then we turn left, and we’ve got

this guy paired with this guy. And so, in general,

whenever you have a North, you turn left with

your two guys. So that’s what happens. Then we hit an East in

the map, and what happens here is this guy turns right,

but this one turns left. This is what you might

call an inside turn. It’s like an inside

reverse fold in origami. And in general, whenever

you have an East, you turn inside like that. So this guy’s paired

with that one, and now this guy’s

paired with that one. They both turn in. And then it’s symmetric. Next one is a w, which is

the opposite of an e, which means you turn out here. And in general, whenever you

have a West, you turn out. And a South, you turn right. So those are the

four possible things you could imagine when you

have a pair of things turning, and those exactly correspond

to N, E, W, and S. So it’s clear what you need

to do in this situation, but there’s flexibility, right? For example, this guy–

when you turn out– here I turned out to the

very next layer, but this could have

turned out to go up here. Would that be OK? Ah, no. If this one turned

out to go up here, that edge up there would be

paired with this one down here. So there’d be a blue

line going like that, and that would be a

crossing situation because that blue line

would cross this one. Because it starts inside

and it goes to outside. So it’s a little tricky. This definitely gives you

some of the layer constraints, but it doesn’t

check for crossings. Which is the big

challenge in this problem. So we’re going to

simplify this diagram. So just think about

top edge views. Forget about map folding now. You can forget about

the previous layers, and we are now focusing

on this reduction. So we’ve got top edge view

converting to ray diagrams. You can see it’s much simpler. This is the ray diagram

of that picture. And essentially–

there’s two ways to think about what we’re doing. Instead of having two edges,

and we track two edges turning, we just want one edge. That’s one thing we’re doing. You can think of that as

tracking the spine instead of the top and the bottom sides. But it’s a little– ray diagrams

are going to get confusing. I’ll just tell you

that right now. Every time I look

at it, I understand it a little bit

more, but it’s not going to be obviously that

this is equivalent to this. I’ll just tell you–

here’s an alternate way to think about it. Basically, the vertical–

the y direction here is going to

be nesting depth. So whenever we go in

like this, we go deeper. So for whatever reason,

I flipped the labeling, but it is indeed East. When you go in, you go down. I should have just moved these

two figures so they correspond, but when you go East you go

down a layer because you’re nesting deeper. And when you go West,

you’re going out, so you go up a layer in this

new weird ray diagram view. And North and South turn out

to not turnaround in this view. We’re just going to

fire a ray downward, and there’s either a

North ray– a blue one– or a South ray– a red one. And so if you follow

this diagram, it’s N-E-W. So first we have an N, which

means we shoot a ray down. Then we have an E, which

means we turn downwards. And then we have a W, which

means we turn to go up a layer. And I haven’t told you what

the constraints are here, but I claim this is a valid

folding just like that one. And it’s obviously a

lot easier to draw. It’s a much slower complexity. But the cool thing

is you no longer have these crossing parts. So let me show you–

first, let me tell you what the constraints are. So in general, you’re going

to have lots of downward rays. This is a North. This is a South. A North, a South. So if you had like N, S,

N, S, in your pattern, it’s just going to

be a straight segment with downward rays

of different colors. First constraint is whenever you

have a an N ray– a North ray– it has to hit another North

ray or just go off to infinity. And the same– South rays

can only hit South rays or go off to infinity. So they line up in

this way, but you can stretch the x-coordinate

to do whatever you want. This corresponds to basically

jumping over a bunch of layers. When you turn in

your folded state, you can skip a bunch of

layers and just go up here. So that corresponds to jumping

over a bunch of folds here. But in particular

we get these things called constrained segments. Constrained segments

are portions of this black spine between

two rays that below it only see black. OK, so for example, this

one is unconstrained, because below it, you

can see off to infinity. So that’s unconstrained. We don’t care about that one. But among unconstrained

segments– these are two

constrained segments– we want that all of the rays

that they see below them– so here I see one red

ray, one blue ray– I want the number of reds

and blues to be equal. So this is valid because

there’s one red, one blue. This one is invalid because

there’s two blue and one red. This turns out to be

the right constraint. Essentially this is saying

however much you spiral, you should spiral. That’s the intuition. So here you’re spiraling

twice, unspiraling once. So you’re trapped inside, and

so these folds cannot actually come together. The rays coming

together correspond to a nice nesting

between two North folds. So it’s not obvious,

but this turns out to be the only

constraints you have. The black should

not cross itself. Constraint segments should

be valid in this way, and blue should hit blue

and red should hit red. So that’s not obvious,

but it’s true, and then you can take very

complicated diagrams like this and simplify them into

these nice pictures. So these are two

different foldings of the same pattern,

which I guess is N-E-N– I can see

that easily here. You could have also

extracted it from here. There’s two foldings

because these two layers could go here in the middle. Or they could be pushed

up to fit in here, and then we get this picture. And in the ray diagram–

you can see this pretty easily– either you have

these n rays just both go off to infinity, and this is an

unconstrained segment so we don’t care about that there’s

only one North ray below. Or, you can extend

the x, because I can stretch the

x parts however I want and make these blue

segments align with each other. And that corresponds

to this folding. So really, all folded

states of the original thing are represented by

the ray diagram. Of course, if I had any

W, this would be valid, but this would not be that. N-E-S– blast from the past. If I had N-E-S, then this would

be blue, this would be red, and so this would be valid. But this would be

invalid, and so on. So it’s obviously a lot

easier conceptually, but you can also– and here’s

a more complicated algorithm. You take a really crazy map. This notation, by the

way, was introduced by Jacques Justin

like late 1980s. You may remember his name

from Kawasaki-Justin theorem. So at the same time he

was looking at map folding and he came up

with this notation, the ray diagram was introduced

in the open problem session in this class two years ago–

or actually five years ago if I recall correctly– by

David Charlton and Yoyo Zhou. And then it was picked

up again two years ago, and finally we took

this ray diagram and came up with an algorithm. So how does the algorithm work? Here’s a ray

diagram– the black, and the red, and the blue. We observe that the blank

space here between the spine stuff– between all the black–

is kind of a tree structure. You’ve got– and

that’s what’s drawn in cyan with the red dots. So if you draw a node every time

you turn around on the outside. Then you say, well, I can get

from this node to this one, so I’m going to draw

a segment there. And I can get from

this node to this one without crossing any black,

so I’ll draw a segment there. That’s sort of it on that side. There’s nothing else down here. That sort of doesn’t count. But here’s there’s

another dot, and I can get from this one

to there by going out here without crossing black. Here to here, here to over

here without crossing black, and so on. So that cyan structure is

a tree– has no cycles. Which in general is good

news for algorithms. Trees are relatively

easy to find algorithms for using dynamic programming. If you’ve seen dynamic

programming for trees, this is not like that. It’s a little different because

we don’t know what the tree is. We have to figure

out what the tree is. But basically, we can

guess the tree recursively. So there’s some first

node– I don’t know, maybe it’s this one–

just guess that. Not randomly, but guess

means try all the options. So you guess some node, and

then OK, we’ve got– maybe we’ve got two subtrees. Maybe we’ve got three. I think that’s about

all there could be. And so, just guessed that,

and then so recursively guess a subtree here and

a subtree here. And each of the sub

trees corresponds to a sub segment of this–

of the original map. The spine, roughly speaking. And roughly speaking,

these portions do not interact with each other. There’s this issue of

how the rays align, and that’s sort of the challenge

in getting this algorithm to work. But you can essentially

locally check whether a subtree

is good enough. That it will interact OK

with a different subtree, and just split this

problem up recursively guessing all the way. Effectively trying all

trees, but in polynomial time instead of exponential time. Forget the running time is

something like n to the 10 or some really big constant,

but at least finally we know 2-by-n maps can be

solved in polynomial time. We give the mountain

valley assignment. We still don’t

know about 3-by-n. That’s the open question, and

these techniques unfortunately don’t seem to apply. You definitely don’t

get a tree anymore. You might get some

nice structure that’s kind of vaguely tree

like, but this was already super complicated. So we’ve gotten stuck here. Any questions? All right. That’s it.

I didn't know there were degrees in Origami ?