Why study Recreational Mathematics?

Why do recreational Mathematics?

1) The line between recreational and serious mathematics is thin. Some of the problems in so-called recreational math are harder than they look.

2) Inspiring. Both Lance and I were inspired by books by Martin Gardner, Ray Smullyan, Brian Hayes, and others.

3) Pedagogical: Understanding Godel's Inc. theorem via the Liar's paradox (Ray S has popularized that approach) is a nice way to teach the theorem to the layperson (and even to non-laypeople).

4) Rec math can be the starting point for so-called serious math. The Konigsberg bridge problem was the starting point for graph theory, The fault diagnosis problem is a generalization of the Truth Tellers and Normals Problem. See here for a nice paper by Blecher on the ``recreational'' problem of given N people of which over half are truth tellers and the rest are normals, asking questions of the type ``is that guy a normal'' to determine whose who. See here for my writeup of the algorithm for a slightly more general problem. See William Hurwoods Thesis: here for a review of the Fault Diagnosis Literature which includes Blecher's paper.

I am sure there are many other examples and I invite the readers to write of them in the comments.

5) Rec math can be used to inspire HS students who don't quite have enough background to do so-called serious mathematics.

This post is a bit odd since I cannot imagine a serious counter-argument; however, if you disagree, leave an intelligent thoughtful comment with a contrary point of view.

# Computational Complexity

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

## Sunday, February 19, 2017

## Thursday, February 16, 2017

### Liberatus Wins at Poker

Tuomas Sandholm (center) and Ph.D. student Noam Brown (via CMU) |

For those unfamiliar with Texas hold 'em

Two cards, known as the hole cards or hold cards, are dealt face down to each player, and then five community cards are dealt face up in three stages. The stages consist of a series of three cards ("the flop"), later an additional single card ("the turn") and a final card ("the river"). Each player seeks the best five card poker hand from the combination of the community cards and their own hole cards. Players have betting options to check, call, raise or fold. Rounds of betting take place before the flop is dealt, and after each subsequent deal.Unlike the computers that defeated the best humans in chess, Jeopardy and go, Liberatus comes directly from academia, from Tuomas Sandholm and his student Noam Brown at Carnegie-Mellon.

Unlike chess and go, poker is a game of incomplete information in many forms.

- Information both players have: the community cards already played.
- Information only one player has: the hole card
- Information neither player has: the community cards yet to be played.

Betting in poker plays the primary role of raising the stakes but betting can also signal what hole cards you have. Players can bluff (betting large amounts without a corresponding strong hand), trying to cause other players to misread the signal. There is no perfect play in poker, just a mixed equilibrium though we still don't know how to compute the equilibrium and even if we could we might deviate from the equilibrium to gain an advantage. Deviating also make you vulnerable.

All of this makes poker a far more complicated game for computers to tackle. But through persistence and new tools in machine learning, Sandholm and Brown have found success.

If history holds up, it won't be long before we have champion-caliber poker apps on our phones. Will we see cheating like has been happening in chess? Will online poker sites just disappear?

What is the next great game to fall to computers? I'm guessing NASCAR.

## Monday, February 13, 2017

### Raymond Smullyan: Logician, Recreational math writer, Philosopher, passed away

Raymond Smullyan was born on May 25 1919 and passed away recently at the age of 97. He was a logician (PhD from Princeton under Alonzo Church in 1959) who did serious, recreational, and philosophical work. I doubt he invented the truth-teller/liar/normals and knight/knave/Knormal problems, but he popularized them and (I suspect) pushed them further than anyone before him.

He was active all of his life:

His last book on Logic Puzzles,

His last book classified (on Wikipedia) as Philosophy/Memoir,

His last Academica book,

His recreational work was of the Knights/Knaves/Knormals/Sane/Insane/ variety.a

Knights always tell the truth.

Knaves always lie,

Knormals may tell the truth or lie.

Insane people only believe false things,

Sane people only believe true things.

He also added a complication: a species that says ALPHA and BETA for YES and NO but

you don't know which of ALPHA, BETA means YES and which one means NO.

Note that a truth teller Insane Knight will answer YES to 1+1=3.

He invented (discovered?) the so called hardest logic puzzle ever. He wrote many books on recreational math. We mention four of them that show the line between recreational and serious mathematics is thin.

He was active all of his life:

His last book on Logic Puzzles,

*The Magic Garden of George B and other Logic Puzzle*s was published in 2015. Wikipedia lists 14 books on logical puzzles, from 1978 untl 2015.His last book classified (on Wikipedia) as Philosophy/Memoir,

*A Mixed Bag: Jokes, Riddles*,*Puzzles*,*and Memorabilia*was published in 2016. Wikipedia lists 8 books in this category, from 1977 until 2016.His last Academica book,

*A beginners further guide to mathematical logic*was published in 2016. (It was a sequel to his 2014*A beginners guide to mathematical logic*.) Wikipedia lists 8 books in this category, from 1961 to 2016.**Recreational Work:**His recreational work was of the Knights/Knaves/Knormals/Sane/Insane/ variety.a

Knights always tell the truth.

Knaves always lie,

Knormals may tell the truth or lie.

Insane people only believe false things,

Sane people only believe true things.

He also added a complication: a species that says ALPHA and BETA for YES and NO but

you don't know which of ALPHA, BETA means YES and which one means NO.

Note that a truth teller Insane Knight will answer YES to 1+1=3.

He invented (discovered?) the so called hardest logic puzzle ever. He wrote many books on recreational math. We mention four of them that show the line between recreational and serious mathematics is thin.

*To Mock a Mockingbird*. This book has logic puzzles based on combinatory logic. Is that really recreational?

*Forever Undecided.*This book introduces the layperson to Godel's theorem.

*Logical Labyrinth*s. This is a textbook for a serious logic course that uses puzzles to teach somewhat serious logic. It was published in 2009 when he was only 89 years old.

A Personal Note: I read the following, from his

*The Lady or the Tiger,*when I was in high school, and I still don't know the answer!:

*My brother told me he would fool me on April Fools Day. I lay awake that night wondering how he would fool me. All day I was worried how he would fool me. At midnight I asked him*

*Hey, you said you would fool me but you didn't He replied April Fools!. To this day I don't know if I was fooled or not.*

*His serious work included the Double Recursion Theorem. (you can write two programs that know both their indices and each others indices) and other theorem in logic. (ADDED LATER: Lipton and Regan have a blog post with lots of great information about Ray S's serious math work here.)*

**Serious Math Work**.**Philosophy.**I'm not qualified to comment on this; however, it looks like he did incorporate his knowledge of logic.

Looking over his books and these points it seems odd to classify his books as the recreational books had some serious logic in them, and the academic books had some math that a layperson could understand

I think its rarer now to do both recreational and serious mathematics, though I welcome intelligent debate on this point.

Before he died, was he the oldest living mathematician? No- Richard Guy is 100 years old. wikipedia claims that Guy is still an active math Guy. Is he the oldest living mathematican? The oldest living active mathematician? It was hard to find out on the web so I ask you.

I think its rarer now to do both recreational and serious mathematics, though I welcome intelligent debate on this point.

Before he died, was he the oldest living mathematician? No- Richard Guy is 100 years old. wikipedia claims that Guy is still an active math Guy. Is he the oldest living mathematican? The oldest living active mathematician? It was hard to find out on the web so I ask you.

## Thursday, February 09, 2017

### The Dichotomy Conjecture

Arash Rafiey, Jeff Kinne and Tomás Feder settle the Feder-Vardi dichotomy conjecture in their paper Dichotomy for Digraph Homomorphism Problems. Jeff Kinne is my academic grandchild--how quickly they grow up.

Keep in mind the usual caveat that this work has not yet been fully refereed and vetted by the community, though there is no reason to think it won't be (though some skepticism in the comments).

A homomorphism from a graph G = (V,E) to H=(V',E') is a function f:V→V' such that if (u,v) is in E then (f(u),f(v)) is in E'. For a fixed graph H, define L(H) as the set of graphs G such that there is a homomorphism from G to H.

If H is just a single edge then L(H) is the set of bipartite graphs. If H is a triangle then L(H) is the set of 3-colorable graphs. If H has a self-loop then L(H) is the set of all graphs.

L(H) is always in NP by guessing the homomorphism. In 1990 Pavol Hell and Jaroslav Nešetřil showed the following dichotomy result: If H is bipartite or has a self-loop then L(H) is computable in polynomial-time, otherwise L(H) is NP-complete. There are no undirected graphs H such that L(H) is not in P or NP-complete.

In 1998 Tomás Feder and Moshe Vardi conjectured that even for all directed graphs H, L(H) is either in P or NP-complete. Rafiey, Kinney and Feder settle the conjecture by showing a polynomial-time algorithm for a certain class of digraphs H.

Details in the paper. The authors recommend first watching their videos below though I would suggest reading at least the introduction of the paper before tackling the videos.

Keep in mind the usual caveat that this work has not yet been fully refereed and vetted by the community, though there is no reason to think it won't be (though some skepticism in the comments).

A homomorphism from a graph G = (V,E) to H=(V',E') is a function f:V→V' such that if (u,v) is in E then (f(u),f(v)) is in E'. For a fixed graph H, define L(H) as the set of graphs G such that there is a homomorphism from G to H.

If H is just a single edge then L(H) is the set of bipartite graphs. If H is a triangle then L(H) is the set of 3-colorable graphs. If H has a self-loop then L(H) is the set of all graphs.

L(H) is always in NP by guessing the homomorphism. In 1990 Pavol Hell and Jaroslav Nešetřil showed the following dichotomy result: If H is bipartite or has a self-loop then L(H) is computable in polynomial-time, otherwise L(H) is NP-complete. There are no undirected graphs H such that L(H) is not in P or NP-complete.

In 1998 Tomás Feder and Moshe Vardi conjectured that even for all directed graphs H, L(H) is either in P or NP-complete. Rafiey, Kinney and Feder settle the conjecture by showing a polynomial-time algorithm for a certain class of digraphs H.

Details in the paper. The authors recommend first watching their videos below though I would suggest reading at least the introduction of the paper before tackling the videos.

## Sunday, February 05, 2017

### The Hardness of Reals Hierarchy

In my last post (here) I defined the following hierarchy (which I am sure is not original- if someone has a source please leave a comment on it)

Z_d[x] is the set of polys of degree d over Z (the integers)

ALG_d is the set of roots of these polys.

ALG_1 = Q (The rationals)

Given a real alpha I think of its complexity as being the least d such that alpha is in ALG_d. This is perhaps a hierarchy of hardness of reals (though there are an uncountable number of reals that are NOT in any ALG_d.)

I then said something like

Clearly

ALG_1 PROPER SUBSET ALG_2 PROPER SUBSET ALG_3 etc.

But is that obvious?

``Clearly'' 2^{1/d} is not in ALG_{d-1}. And this is not a trick- YES 2^{1/d} is NOT in ALG_{d-1} But how would you prove that. My first thought was `I'll just use Galois theory' And I am sure I could dust off my Galois theory notes (I had the course in 1978 so the notes are VERY dusty) and prove it. But is there an elementary proof. A proof a High School Student could understand.

How to find out? Ask a bright high school student to prove it! Actually I asked a Freshman Math Major who is very good, Erik Metz. I thought he would find a proof, I would post about it asking if it was known, and I would get comments telling me that OF COURSE its known but not give me a reference (have I become cynical from years of blogging. Yes.)

But that's not what happened. Erik had a book

Hence the hardness of reals hierarchy is proper. For a write up of just the proof that

7^{1/3} is not in ALG_2 (which has most of the ideas) see this writeup

Z_d[x] is the set of polys of degree d over Z (the integers)

ALG_d is the set of roots of these polys.

ALG_1 = Q (The rationals)

Given a real alpha I think of its complexity as being the least d such that alpha is in ALG_d. This is perhaps a hierarchy of hardness of reals (though there are an uncountable number of reals that are NOT in any ALG_d.)

I then said something like

Clearly

ALG_1 PROPER SUBSET ALG_2 PROPER SUBSET ALG_3 etc.

But is that obvious?

``Clearly'' 2^{1/d} is not in ALG_{d-1}. And this is not a trick- YES 2^{1/d} is NOT in ALG_{d-1} But how would you prove that. My first thought was `I'll just use Galois theory' And I am sure I could dust off my Galois theory notes (I had the course in 1978 so the notes are VERY dusty) and prove it. But is there an elementary proof. A proof a High School Student could understand.

How to find out? Ask a bright high school student to prove it! Actually I asked a Freshman Math Major who is very good, Erik Metz. I thought he would find a proof, I would post about it asking if it was known, and I would get comments telling me that OF COURSE its known but not give me a reference (have I become cynical from years of blogging. Yes.)

But that's not what happened. Erik had a book

*Problems from the Book*by Dospinescu and Andreescu that has in it a lovely elementary proof (it uses Linear Algebra) that 2^{1/d} is NOT in ALG_{d-1}.Hence the hardness of reals hierarchy is proper. For a write up of just the proof that

7^{1/3} is not in ALG_2 (which has most of the ideas) see this writeup

## Thursday, February 02, 2017

### We Are All Iranians

A solidarity rally held at Georgia Tech today |

We have nine Iranian Ph.D. students. It was already difficult for them to leave the US and return and with the new executive order essentially impossible, even for family emergencies. One expressed disappointment “Why did we even bother to come to the United States to study?”

We also have a young Iranian professor, a very successful computer architect and my first hire as chair, in the final stage before getting his green card now on hold. If things don’t change he and his wife may be forced to leave the country they now call home. That would be a huge loss for Georgia Tech and the United States.

This is not the America I believe in.

## Sunday, January 29, 2017

### What was the first result in complexity theory?

Let Z_d[x] be the set of polynomials of degree d over the integers.

Let ALG_d be the set of roots of polys in Z_d.

One can easily show that

ALG_1 is a proper subset ALG_2is a proper subset ...

and that there are numbers not in any of the ALG_i (by a countability argument).

I began my ugrad automata theory course with this theorem (also a good review of countability- I found out, NOT to my surprise, that they never really understood it as freshman taking Discrete Math, even the good students.)

I presented this as the

Complexity theory is about proving that you can't do BLAH with resource bound BLAHBLAH.. We will distinguish it from Computability theory by insisting that the things we want to compute are computable; however, if someone else wants to argue that (say)

Here are other candidates:

1) sqrt(2) is irrational. This could be considered a result in descriptive complexity theory.

2) The number of primes is infinite. If you view `finite' as a complexity class then this takes PRIMES out of that class.

3) You cannot, with ruler and compass, trisect an angle, square a circle, or double a cube. This seems very close to the mark--- one can view ruler-and-compass as a well defined model of computation and these are lower bounds in that model.

4) There is no quintic equation. Also close to the mark as this is a well defined lower bound.

5) In the early 60s the definition of P (Cobram) and of DTIME, etc (Hartmanis-Stearns). The result I would point to is the time hiearchy theorem. While these results are much later than those above, they are also far closer to our current notion of complexity.

6) I'm not sure which paper to point to, but Knuth's observation that one can analyse algorithms without running them. This is more algorithms than complexity, but at this level the distinction may be minor.

7) Cook-Levin Theorem. Probably not the first theorem in Complexity, but certainly a big turning point.

I urge you to comment with other candidates!

Let ALG_d be the set of roots of polys in Z_d.

One can easily show that

ALG_1 is a proper subset ALG_2is a proper subset ...

and that there are numbers not in any of the ALG_i (by a countability argument).

I began my ugrad automata theory course with this theorem (also a good review of countability- I found out, NOT to my surprise, that they never really understood it as freshman taking Discrete Math, even the good students.)

I presented this as the

*first theorem in complexity.**But is it? I suspect that the question*

*What was the first result in complexity?**has no real answer, but there are thoughts:*

Complexity theory is about proving that you can't do BLAH with resource bound BLAHBLAH.. We will distinguish it from Computability theory by insisting that the things we want to compute are computable; however, if someone else wants to argue that (say)

*HALT is undecidable*is the first result in complexity, I would not agree but I would not argue against it.Here are other candidates:

1) sqrt(2) is irrational. This could be considered a result in descriptive complexity theory.

2) The number of primes is infinite. If you view `finite' as a complexity class then this takes PRIMES out of that class.

3) You cannot, with ruler and compass, trisect an angle, square a circle, or double a cube. This seems very close to the mark--- one can view ruler-and-compass as a well defined model of computation and these are lower bounds in that model.

4) There is no quintic equation. Also close to the mark as this is a well defined lower bound.

5) In the early 60s the definition of P (Cobram) and of DTIME, etc (Hartmanis-Stearns). The result I would point to is the time hiearchy theorem. While these results are much later than those above, they are also far closer to our current notion of complexity.

6) I'm not sure which paper to point to, but Knuth's observation that one can analyse algorithms without running them. This is more algorithms than complexity, but at this level the distinction may be minor.

7) Cook-Levin Theorem. Probably not the first theorem in Complexity, but certainly a big turning point.

I urge you to comment with other candidates!

## Thursday, January 26, 2017

### 60 years of Eric and Mike

As I checked in at the Holiday Inn in New Brunswick Wednesday night, they asked me if I had stayed there before. I said it has been a while and they looked in their computer: October 2007. I was last at DIMACS for the Workshop on the Boundary between Economic Theory and Computer Science, the closing workshop of the Special Focus on Computation and the Socio-Economic Sciences which Rakesh Vohra and I had organized. DIMACS, the Center for Discrete Math and Computer Science at Rutgers, started as an NSF center and I went often, even serving on the executive committee when I worked at NEC in the early 2000's. So an odd feeling to be back after ten years.

But back for a good reason, the DIMACS Workshop on E+M=C

^{2}, the joint 60th birthday celebration for Rutgers Professors Eric Allender and Michael Saks. A great turnout of Eric and Mike's former colleagues and students. I've known both Eric and Mike for many years but it is Eric I've had the closest connections to. Eric and I share many research interests, especially in Kolmogorov complexity. I took over from Eric as chair of the Computational Complexity conference and Eric took over from me as editor-in-chief of ACM Transactions on Computation Theory. Combined we've attended 61 of the 31 complexity conferences so far (I missed 2012 in Porto) and many Dagstuhl workshops and other meetings together on four continents. But we've oddly enough never co-authored.

Congrats to Eric and Mike and their careers worth savoring.

Subscribe to:
Posts (Atom)