Episode 7: P vs. NP

Mmm...the world of computer science; where mathematics meets application in the purest sense.

A little fact about me: I don't really like applied math at all. I have nothing against it, that specific area of math just isn't for me. I seem to lose interest as soon as the math I'm learning has an application. However, computer science is the only application of mathematics where I don't totally lose interest. I think it's because the "application" is just more mathy goodness :)

So! The biggest question in the world of computer science is:

Does P=NP?

No one knows, and there will be some big bucks awarded to whoever finds out what the answer is.

But what does it mean? What is P? What is NP? And who cares if they are equal or not?

It's actually not as scary as it sounds (in general, math is not as scary as it sounds...except for RFM, that's for sure scary...).

Ok, so basically P represents the set of all problems that can be found in polynomial time, and NP represents the set of all problems whose solutions can be verified in polynomial time.

Polynomial time just means that the time needed to find the solution has a polynomial relationship with the size of the problem.

The question, does P=NP? asks whether all problems which can be solved in polynomial time, can also be verified in polynomial time.


So what's the big deal? Why does it matter if they're equal or not?

Well, if P=NP then it would transform mathematics, and the world. It would mean that computers could find proofs of theorems which have proofs of reasonable length (so would mathematicians be out of a job?). It would also cause a lot of problems in security on the internet. A lot (ok, actually ALL) security systems on the internet are running on the fact that P doesn't equal NP. If it turned out they did, well, let's just say: massive chaos.

If P≠NP then it wouldn't be as exciting (and definitely not as surprising), but it would still be useful to mathematicians and computer scientists alike. It would allow people to show, formally, that many common problems just can't be solved efficiently. This result would allow researchers to focus their attention on more practical problems. The general belief is that P≠NP.


So why is this question so hard? Why can't anyone figure it out?

The answer to this question is actually quite simple: we don't know enough, and our knowledge base is too small. Most sciences who have studied this problem think that we just don't have the right tools and proof methods right now in order to approach this and solve this correctly.

That sounds simple enough, right? Humans just aren't smart enough. Yet.

It just needs a fresh look, and maybe some new ideas. Who knows, maybe you'll solve it :)

LADIES & GENTLEMEN!!!

I HAVE A PUBLIC SERVICE ANNOUNCEMENT!

I would like everyone to know this very important fact:

I HAVE THE WORLD'S
BEST PARENTS!

I just received the best care package ever. It included (but was not limited to) Old Bay Chips, pistachios, Snyder's Honey Mustard pretzels, dried mango, spring shirts, orange slices, mmm...


I love them ♥



And don't worry, I shared :)

Loud & Clear.

While I have suspected this for quite sometime, I have come to the resounding realization that life is completely miraculous.

At least that’s the loud and clear message that I have gotten from God the past 3 and a half months of my life.

Here we are, existing together, will all types of “things” happening to us. We find ourselves in certain circumstances, be it a tragedy, a blessing, or just about everything and anything else that life wants to throw at us.

But we all survive, and we all turn out just fine (for the most part); and some of us are even lucky enough to experience little miracles :)



Isn't it so fantastic that we find ourselves in situations that seem nearly impossible to us but everything works out in the end? Isn't it comforting to know that God would never give us something that He knows would be too much for us?

I guess the tricky part is to remember that; to remember that no matter how rough life gets, we can always pull through. We just have to have faith.

Hangtalan Kedd: Iskolám Edition

"Hey, I've got testosterone..."

Vienna was beautiful. Absolutely beautiful.

We spent 24 hours walking around seeing beautiful buildings, gorgeous gardens, and pretty palaces.

When we first arrived, we stopped by the hostel, put our stuff down, and then went exploring. We even made a new Hungarian friend who joined us on part of our adventure.









We saw a lot of tulips. A LOT. Basically every place that had flowers had tulips. They were everywhere, and I was in love.






Saturday night we were all pretty tired so we went to bed early (we know, laaame). But Sunday we woke up early and Kylee and I went to mass at St. Francis of Assisi Church.




It was a beautiful church and the service was really nice. Before mass started the priest came up and introduced himself to us. He asked where we were from and we explained that we were from USA but studying "math" in Hungary. He was from England and he told us that English people think that Americans can't do mathematics because they can't even say it correctly. He explained that it isn't "math", but "maths"--because the word is plural. We laughed :)


After church, the four of us (Kylee, Ranjan, Caitlin, & I) went to the Schoenbrunn Palace. It was gorgeous. We even got to see some Storm Troopers and various other Star War characters (yes, I was as shocked as you are).




We spent the remainder of the day walking around, sleeping on the grass, and enjoying the absolutely perfect weather. Needless to say, I got sunburnt, but it was totally worth it :)





We decided that we were glad we didn't go to Vienna earlier in the semester. As pretty as it probably is in the snow, I don't think it could have been more beautiful than how we saw it ♥

Painting Picnics

Spring has finally hit, and it’s hitting hard. The flowers are blooming, the trees are vibrant green, and the air is full of vivacious smells.

You know what this girl loves to do on beautiful Spring days?

Go on picnics ♥

The thing is, I didn’t want it to be any ordinary picnic. Seeing as how nothing about my adventure is “ordinary”, I didn’t want to break the tradition. I wanted to add a much needed twist. I wanted us to get in touch with a part of ourselves that we haven’t been in touch with in quite a while. So I came up with this brilliant idea:

“Let’s finger paint!!!!”

Ok, ok, I know: it sounds childish and ridiculous; but I mean, that’s kind of the point here! A few people laughed at me when I first mentioned this idea, but just think about it for a few minutes...

Here we are, in a foreign country, with awesome friends, in the midst of spring, and our brains are going to explode from weeks filled with massive amounts of math.

It didn’t take much convincing at all to get some of these kids onto the band wagon.

So we went on a finger painting picnic.








And it wasn’t just finger painting. It was also, “get as much paint on your clothes because you don’t have any adults yelling at you and you are finally old enough to do what you want with paint” painting :)





I think we got a few masterpieces made, and to say that it turned into a giant (beautiful) mess would be the understatement of a lifetime.




It was loads of fun. I had an awesome Friday, to say the least. Today I'm headed to Vienna, so I will be sure to update you soon about that.



I hope that each of you get in touch with your inner child when life seems too much sometimes. Take it from me, it's totally worth it...

Episode 6: Combinatorial Number Theory

So last week I asked:

Does every number have a multiple that starts with the number 2004?

Well, indeed, the answer is....

YES!

That's totally cool, right? Every single number has a multiple that starts with 2004. Every single number. Even numbers that are 2004^20042004 digits long, still have a multiple that starts with 2004.

Don't worry, if you don't believe me, I'm going to prove it to you.


First, I need to tell you about a couple of things so you can understand the proof.

The first is this way cool concept called the Pigeonhole Principle. It states,

If n+1 pigeons are trying to find a home in n holes,
then at least one hole contains two or more of the pigeons.

It seems kind of silly, but it is a extremely useful in a lot of mathematics.



The second thing is a little bit more tricky, so I'm sorry if I lose you.

Consider a number, like 6. Then every other number is said to be congruent to either 0, 1, 2, 3, 4, or 5 "mod 6". This means that give me any number (integer), and I will tell you what it is mod 6 (you divide it by 6, and the remainder is the number mod 6).

17 is congruent to 5 mod 6 (17/6= 2 remainder 5)
36 is congruent to 0 mod 6 (36/6=6 remainder 0)
1679617 is congruent to 1 mod 6 (1679617/6=279936 remainder 1)--ok, excessive, sorry....
24 is congruent to 0 mod 6 (24/6=4 remainder 0)
74 is congruent to 2 mod 6 (74/6=12 remainder 2)
and so on and so on and so on...

We will note that if something is 0 mod 6, then it is a multiple of 6. Since every number can be written as one of these 6 numbers, these 6 numbers are called the residue classes of 6. Therefore, every number falls into one of these 6 reside classes for mod 6. This is true for every number, n (meaning, every number, n, has n residue classes).

Now that you know these two things, let's proof this super cool fact!



Proof:

For any number, n, let’s look at the numbers in the form

200420042004………….2004 such that it has 4n digits
20042004………….2004 such that it has 4n-4 digits
2004………….2004 such that it has 4n-8 digits
all the way to
2004 such that it has 4 digits

We can see that there are n numbers on this list.

If one of these is divisible by n, then we are done because we have found the multiple of n that starts with 2004. Therefore, let’s assume that none of these numbers is divisible by n. Now, if we use the pigeonhole principle, and allow the residue classes of n to be the holes we can see that we have n-1 classes, and n numbers to put into the holes (because we don't have the 0 hole, since we are assuming it's not divisible by n).

By the pigeonhole principle, at least 2 numbers from the list must be in the same hole (or the same class). When this occurs, the difference of those 2 numbers will be 0 mod n, or divisible by n (by the properties of residue classes). This number will also start with 2004 (because of the way we constructed the list). Thus, we have a number that is divisible by n and starts with 2004.

THUS, we have shown that every number has a multiple starting with 2004! (Usually a little box goes right here to signify the end of a proof, but I don't know how to make that so I'll just do a heart.) ♥


That's pretty cool, right?

The Comforting Sting of Nostalgia

A few days ago I stumbled upon this song. I could not help but get that aching twinge of nostalgia.

When I was younger, much younger, my Uncle Phil used to play me this song. During Thanksgiving, or Easter, or just random family visits, I would occasionally here this song playing for me.

I was never sure where it came from, or what inspired him to do it (I mean, besides my name being Lydia...), but it always made me feel special. And what little girl doesn't want to feel special?

I don’t think I ever thanked my Uncle Phil for this, in which case I am terribly sorry. So, a much delayed and overdue appreciation, but an appreciation nonetheless,

Thank you, Uncle Phil.
It will forever be one of my favorite childhood memories ♥.

Finding this made me realize how much I look forward to the day where the little things remind me of my time here, in Budapest. I look forward to stumbling upon photos, remembering an inside joke, or hearing a song that will bring that warm, comforting sting of nostalgia to my overflowing heart...

Sometimes I still can't believe that I'm making these kinds of memories...

Hangtalan Kedd: Happy Birthday, Hulk Edition

"Who goes to a waterpark on a Sunday?!"

AquaWorld was a giant success!!!!

I felt like such a little kid. It was so much fun.

Here are a few pictures, courtesy of Jolene ♥

3 Musketeers

Jolene ♥

The Girls ♥

BSM :)

AquaWorld!

So who would have thought that the biggest indoor waterpark in all of Europe was located right here in Budapest?!

Not me.

Tomorrow: AquaWorld.

Episode 5: Ponzi Scheme Cont.

So, remember three weeks ago when I mentioned Madoff?

Well, I figured I should let you know in what kinds of infinite worlds Ponzi Schemes will actually work (finally!).

As it turns out, if our world was an infinite lattice, the Ponzi Scheme would still not work. It doesn't work for all infinite worlds. There are restrictions.

A necessary, but not sufficient, condition for a Ponzi Scheme to be successful is an infinite world with exponential growth.

You can see this for the infinite binary tree: there was exponential growth between the points.

We can get even more specific than that, though. We know exactly when a Ponzi Scheme will work for a specific graph (or infinite world). If a graph has no obstruction, then the graph is a Ponzi Scheme.

What does that mean, exactly?

Well, it means that large chunks of the graph have boundary points which are small. So small, in fact, that if k_n is a boundary point for all n, then |2k_n|/|k_n| converges to 0 as n goes to infinity.

Cool, huh?





To think about until next week:
Does every number have a multiple that starts with the number 2004?

A Struggle.

For one reason or another...

Some days are harder to get through than others.

Some days school just seems too much for me to handle.

Some days I feel like a failure and a disappointment.

Some days I don't understand at all what God's plan is for me.

Some days I feel like my life is a giant mess.

Some days I can't help but think that I made a wrong turn somewhere and there is no way to fix where it went wrong.

Some days I realize how scared I am of life and all the possibilities that it has to offer.

Some days I think that the strong-face that I put on does a poor job of hiding the broken, terrified girl that I really am.

Some days I totally understand why it is that most of the closest, most important people in my life have ended up leaving me.

Some days I just want to give up...



This week has been quite a collection of those days.




A wise person told me some time last week,

“Sometimes God lets us make a mess out of our

lives so we have to ask Him to help us clean it up...”

As happy as I am trying to be, as put together as I may seem to most people, and as ridiculously grateful as I am for everything that I have in my life and everything that is to come, I have to say...

God, I need a broom...and maybe some Windex...

*And thus ends the most self-pitying blog post that I will hopefully ever write.

MORE Wise Words from FUN

"If you just take a couple of Borel sets...you know, countably many..."


"For the first time in your life, an infinite object in your hand. Ok, really, it's in your head, you can't hold these things."


"That's the point of your life: when you understand infinite dimensions..."


"That's the main point in math: to have trendy, sexy questions!"


"What is the shape of the universe? You know it could be nonorientable..."


"Your eye is a finite σ-algebra; the world is an infinite σ-algebra. This is the philosophy."


"The Radon-Nykodym Theorem says that even if you're in the Matrix, you will never know it..."


"I'm not sure if you see...because you should not a little bit."


"It's an infinite dimensional space; it's kind of complicated."


"Give me your fantasy of linear transformations! Please don't give me the zero."


"That's why it's hard to imagine infinite dimensional spaces: because the unit ball is not compact."

Hangtalan Kedd: New Friends Edition

Dad, You'd Be So...

...proud?





This thing started out as a disaster.

A legitimate disaster.

Besides the fact that I didn't have the right cut of meat, and I had no garlic crusher, I had a much bigger problem.

I had no black beans.

NONE.

I was freaking out.

Nobody understood why I was so worried. "The meal will still be delicious," they kept telling me. "It's just black beans, can't you just use another kind of bean?!" They didn't understand: having no black beans in a Cuban meal is like having a meatloaf with no meat. It just doesn't happen. It doesn't make sense.

I checked about 3279183271 million stores, and I just could NOT find any. Apparently I just don't know where to look because other people had seen them before. In fact, someone was ridiculously nice enough to let me have the rest of his black bean stash (I know, he will never know the great deed he did).




The only problem was, it was no where near enough beans to serve everyone. So, I had to give in and go to the store and buy another type of bean to go along with it. I don't even know what the bean was called, but Stephanie called them the "ghetto beans".




As it turns out, everything went great (when it comes to me cooking, things usually turn out quite nicely). The pork was delicious, and I definitely pulled a Larry King:

When the pork was ready, I found myself cutting it up and eating more than I was putting on the serving plate (with a Rum & Coke in hand).




I ended the night with a nice Cuban (a cigar, not a boy ;) ), and a Skype date with my parents so they could meet my friends and hear about how delicious the food was :)

It was as close to a perfect Sunday night as I need to make me happy ♥




You know if this whole Mathematician thing doesn't work out...I could totally see myself having a restaurant...






...but what would it be called?

My Deepest Apology...

I'm so terribly sorry that I have been slacking on my Math Episodes. Yesterday was a horrible, horrible day.

I felt like I was going to die.

While I spent most of the day in bed or in the bathroom (I'll spare you the details), I think it was just a 24 hour bug. Today is much better.

This morning, in fact, I woke up at 9 and got stuff done! I went to the Butcher Shop, where I was sufficiently hit on by the meat man, and bought my pork shoulder (no picnic pork shoulder, but hopefully I can make it work).

Then I went to the Asian Market and bought saffron. Real Spanish Saffron. So real, in fact, that it cost more than the meat...

I plan on making Cuban Pork with Black Beans & Rice tomorrow for Easter Dinner (since I couldn't make it last Sunday). I now have everything I need except the black beans.

I promise that the Math Episodes will continue next week.

As for now, I'm going to continue to be excited (and nervous) to make this Cuban meal tomorrow (for close to 25 people!). Eek!

Mmm...mojo :)

More Than I Can Chew...

In the history of my academic life, I have always taken a schedule that I think is way too hard. Always. I always push myself and I always throw myself into something that seems close to impossible.

But I always surprise myself. I always come out of it learning more than I thought was possible, doing better than I thought I would ever do, and it just pushes me to do it again.

I should have known that this semester (where nothing is staying the same) would be different.

It seems that taking 5 math classes (2 of which I do not have the right prerequisites for) is too much for me.

I admit defeat...Actually, my grades admit defeat.

As much as overcoming my hard schedules has pushed me in the past, I feel like this will motivate me even more.

I just need experience, and the right kind of thinking.

But still...what a horrible feeling...

Dear Time,

I would absolutely love it if you would slow down.

Can I go back to when days seemed long and weekends seemed like they would never come?

How about just a little bit slower? That would be fantastic.

My adventure would greatly appreciate it, seeing as how it never wants to end...

It seems that I have less than 60 days left in this wonderful, beautiful country.

I have so much more to do! I have so much more to see!

Just think about it...

Love Always,
Lydia Ann ♥

An Easter to Remember...

At 6 AM on Sunday morning, I woke the 13 other BSM train passengers to wish them a Happy Easter!

How did I cushion the blow? I handed out individual clues, so that they could find each of their hidden Easter bags (we didn't have any baskets) throughout the train.

It was great. I got to share my favorite holiday with really special people.

But I still had an ache in my heart. I missed my family more on Sunday then I have since I have left home.

I wanted to be in Frederick. I wanted to be wearing my yellow Easter dress and finding my Easter egg on the Palmer's farm. I wanted to be eating my Mom's carrot cake and my Dad's Cuban pork. I wanted to be in Church. I wanted to be surrounded by family.

While everyone was enjoying their candy, I went into an empty car on the train (there was really no one else on this train) and just prayed. For a while. I thanked God for everything He has given me. I asked for grace and patience. I prayed that my family was going to have an amazing Easter. It was just what I needed to calm me down.

After this, my day kept getting better and better.

We had to transfer trains in Beograd, Serbia; we were stuck there for about 2 hours. So, we decided to try and grab some real food and explore Serbia a bit.

After getting some food, I got some Easter flowers (courtesy of Paul and Al ♥)! I love flowers. They were (are) beautiful. And they smelled (smell) amazing.


The rest of the train ride smelled amazingly. I couldn't help but have a huge smile on my face every time I looked by the window and saw them :)

Caitlin and I got home to our apartment around 7 pm and my day ended perfectly (I couldn't have asked for a better ending). Not only did I get to Skype with my sister (and hear my adorable nephew say, "Bye Tia", for the first time), and not only did I get to Skype with my parent's to wish them a Happy Easter, but my Dad brought his computer to the Palmer's farm and I got to see my whole family (well, not my whole family, but it was good enough).

It.was.wonderful.

Any amount of homesickness I had from earlier disappeared.

It was a great way to end an Easter that I will never forget.

A Glorious Bite

One of my old favorite songs by Snow Patrol has a really great verse:

Do the things that you always wanted to;
Without me there to hold you back, don't think, just do.

More than anything I want to see you go
take a glorious bite out of the whole world.

I was listening to this song on the train to Sikia yesterday, and I realized that I'm really starting to live my life to the absolute fullest.

I feel like I'm in paradise. The Greek people are so wonderful. We arrived to this town (that we just randomly found) yesterday and they were so excited to see Americans (they said they haven't seen any in this town for over 15 years).


I feel like the luckiest girl in the world for being able to have this experience. I was talking to Stephanie on the beach yesterday, and she asked who I wished I was sharing this gorgeous place with from home. And I would definitely, without a doubt, want my whole entire loud, wonderful, beautiful family (every single one of them) here with me.


But, since they can't be here with me (unfortunately), I just want you all to know:

I'm taking a giant, delicious, glorious bite ♥

*Unfortunately I will not be posting a Math Episode tomorrow. Regular programming will return on Friday, April 9th. I hope you all have a very blessed Holy Thursday & Good Friday.