Flying Pigs Unsafe at Any Speed

Take a moment and imagine a flying pig. Do you see a pig with tiny wings lazily guiding along. But pigs are not particularly slow animals as anyone has seen a pig race at a county fair can attest to that. So why not in the air shouldn't a pig go faster than an unladen African swallow?

I have a point discussing the fastness of a flying pig. Consider my favorite flying pig, P = NP. I would put more probability on an actual flying pig (thanks CRISPR) than polynomial-time algorithms for traveling salesman.

Sometimes I get in the following conversation:

AI person: The P v NP problem is irrelevant as we have machine learning and SAT solvers and we can for all practical purposes solve NP-complete problems.
Me: If P = NP we can solve AI!
AI: If P = NP it's likely to have a very slow poly-time algorithm with high exponents and constants and be for all practical purposes useless.

Let's break that down. The claim is E(running time of SAT|running time of SAT is poly) = cn^k for some large c and k. First of all you are conditioning on a probability zero event. Beyond that nearly all the known problems we know that sit in polynomial time have practical efficient solutions. So under the assumption that SAT is one of these problems, why shouldn't the same rule apply. You've already made the assumption we can reduce its running time from exponential to polynomial, so why would it stop at some high polynomial?

If we are going to talk about the hypothetical flying pig P = NP world, let my algorithms run fast.

Problems with a Point: Exploring Math and Computer Science

As you can see from Lance's tweet


               Problems with a Point: Exploring Math and Computer Science
               by Gasarch and Kruskal

(ADDED LATER- the World scientific website has more info than amazon and has a table of contents, so here it is: here)

is now available! The tweet says its $68.00 but that's hardcover- paperback is $38.00 (are covers that expensive) and if you like your books already broken in, there are some used copies for $89.00. Makes sense to me (no it doesn't!). Could be the topic of a blog post (probably already was).

Okay, so whats in the book?  One of my favorite types of blog posts is when I make a point ABOUT math and then do some math to underscore that point.  I went through all of my blogs (all? No, I doubt I did that) and picked out blogs of that type. With Clyde's help we EXPANDED and POLISHED and GOT THE MATH RIGHT (in some cases I didn't have any math so we had to supply it).

When I first got a copy (about a month ago) I just couldn't stop reading it. I really like it! This is a non-trivial remark -- often authors get tired of their book, or after a while and wonder things like ``why did I write 300 page on the muffin problem? What was I thinking?'' So the fact that I am very pleased with it is not obvious. Does it mean you will?

If you ever thought `I wish bill would clean up his posts spelling and grammar AND expand on the math AND make it a more cohesive whole' then buy the book!

I will in future posts describe more about writing the book, but this is probably my last post where I plug the book.

bill g.

Extra! Extra! Read all about it!

Last weekend I saw the documentary Joseph Pulitzer: Voice of the People. Pulitzer, as you probably know from the prize named after him, was a major newspaper publisher in the late 19th and early 20th century. He ran two papers, the St. Louis Post-Dispatch and The New York World. The World at one point took on massive proportions, including sheet music of the latest tunes and dress patterns of new fashion that one could make at home. The World was the Internet of the turn of the 20th century.

The movie mentioned the many editions of the paper during the day, including the extra edition. An extra edition came out because of some major breaking news story. Back then newspapers would drum up minor stories to sell extra editions but they tended to disappear over time.

Which brings me to Monday, August 19, 1991. Hard-line members of the communist party of the USSR attempted a coup to take over the government from Mikhail Gorbachev. To us in the US, this seemed like the cold war which appeared to be coming to an end might rekindle. At the time I lived in Chicago and on that Monday the Chicago Tribune ran an extra afternoon edition talking about the coup. The return to the cold war didn't happen. Within a couple of days the coup failed and if anything hastened the dissolution of the Soviet Republic.

That was probably the last of the extra editions. By the time of the next major historical event, ten years and twenty-three days later, we had the Internet and cell phones and one no longer needed a newspaper to tell you the world has changed.

Using `who will be the dem VP choice' article in class

I recently read an absurd article that speculated on who the Democratic VICE prez nominees will be. Yes, you read that right, VICE Prez. Gee, wouldn't knowing who the Prez nominees was first help. But leave it to Nate Silver and company to have a fascinating yet... premature article on this. Here is the link: article on who will be Dem VP nominee.  Its hard enough to pick the VP when the Prez is known! I did a blog on how badly intrade would do on predicting VP, here. I didn't predict that intrade would go out of business (`intrade' was short hand for `betting markets' just like `Uber' is shorthand for `hailing a car with your phone'- I wonder if the term `Uber' will still be used if they go out of business?)

After reading I thought

Wow- there are so many If-Then clauses in this that I could make half a lecture about it for my Discrete Math class where we are talking about Prop. Logic.

I emailed the students to read it, and we had a lively discussion. I made sure it was a non-partisan discussion. Realize that a statement like:

If the Prez is a female then the VP will likely be a male because it is thought, righly or wrongly, that all-female ticket can't win

is not partisan or sexist, it is stating an opinion about how voters would go. It may be incorrect, but its not offensive.

Here is what the class thought the article was saying (and I think they are right) expressed in Logic.

Note one other thing-- the Prez nominees  might not be the choice of the party (Trump wasn't the choice of the Rep party in 2016, though not clear who was, see here) but the VP really will be since (I think) the party has more control over that.

If the Prez Nominees is female then the Vice Prez nominee will be male. (I agree)

If the Prez Nominees is white mail then the Vice Prez nominee will be either female or non-white but not both. (Great question to express that as symbols. Not sure what I think- the thought is that two white males will be odd since so many of the candidates are female or non-white. Having said that, in recent years the VP has NOT been someone else who ran:  Clinton-Keane, Keane had not been a candidate, Trump-Pence, Pence had not been a candidate, Romney-Ryan, Ryan had not been a candidate, Obama-Biden, Biden had been a candidate briefly in 2008, but this was not one of these `lets unite the party by picking by OPPONENT to be VP', McCain-Palin, Palin had not been a candidate. Kerry-Edwards. YES- Edwards had been a serious candidate in 2004, though some think he was running for VP all along since he never said an unkind word about his opponents)

Prez from one of the coasts IFF VP from the center. (I won't go over the list again, but this has been less of a thing since Clinton-Gore were both from flyover states.)

Ideology- If Prez is establishment then VP is leftists. (Not sure these terms are so well defined to say this, and their are other ideologies as well, not sure how they fit in.)

If Prez lacks Fed Experience then VP should have Fed Exp. (Quite common: Obama-Biden, Romney-Ryan, Clinton-Gore, Bush-Cheney)

If Prez has fed experience than nothing can be deduced about VP Fed Exp.

If Prez lacks gravitas then VP should have gravitas (tricky! Don't want the VP to outshine the Prez!)

Absolute statement: VP should not outshine prez. A Kangaroo ticket is when the people prefer the VP to the Prez (Dukakis-Bentsen had this problem. Kerry-Edwards might have).

If Prez is boring then VP should be exciting. But again tricky! (I think that was why McCain picked Palin. And she was exciting, but not really in a good way. Couldn't he have picked someone exciting, and perhaps female who was, you know, Qualified?)

VP's like doctors: do no harm.

VP from Swing state helpful but not necc.

Bad to have a VP who is a senator from a state where the Governor is republican and picks the replacement senator.

VP should be someone who the country can picture being president without laughing. I am not talking ideology I am talking about seriousness and experience. Palin was the only one in recent memory who even voters of her party worried that she was not up to being president. One pundit defending the choice talked about how McCain was healthy and hence Palin wouldn't become prez so don't worry about it. NOT reassuring! Quayle was also not seen as serious, though not as much as Palin.

If Prez is old then VP mattes more(?)

Many of the above depend on who the Prez is. And that is one of the points: one can write down a long prop formula with many IF-THEN's to determine who properties the VP will have, and then

1) When the Prez is picked many of the variables are set and hence the formula becomes much easeier and

2) Could STILL be wrong!

MY prediction: my last two predictions have been wrong so I am reluctant go predict anything. But I will tell you my WRONG predictions and then my current one

I predicted Paul Ryan would be the Prez Nominee in 2016. He didn't even run.

I predicted that Al Franken would be the Prez Nominess in 2020- he understands TV and was an entertainer, so he could match Trump. Whoops.

So with that sterling record I predict: Prez: Cory Booker, VP: Beto

I am NOT a pundit- so what I predict is not what I hope happens.  What do I hope? In the interest of full disclosure (gee, shouldn't that have come at the beginning) I admit that I want to see Trump lose but I have no idea what makes someone `electable' nowadays.

The iPhonification of Everything

So you've got an iPhone XS in Space Grey. Congrats, so do 20 million other people. Maybe you have different cases but otherwise the hardware in all these phones are virtually identical. Yet you can tell with a glance that this is your phone. You can personalize apps and other elements of the home screen. It's your calendar and email and music.

What? You've dropped your phone over Niagara falls. Luckily you've backed up your data. So you go back to Apple and buy another Space Grey iPhone XS and restore your data. Physically it's a completely different phone but for all practical purposes it's though you still had the original phone. Your phone is not defined by the device but the data that resides on it.

It's not just phones. I can log into Google on anyone's Chrome browser and it will feel like my machine.

Now we've all heard about a future world where nobody owns cars and we get driven around in self-driving Ubers, Lyfts and Waymos. One argument against this world is that people feel connected to their cars and unwilling to commute in some generic vehicle. But one can also imagine the car knows who you are, knows how you like your music, your lighting, how you adjust your seats even how your car drives. It becomes your car. Maybe even has electronic bumper stickers that change to support your political party.

You can imagine the same for hotel rooms, your office, maybe even your apartment. It won't replicate your dog (or will it?) but as we get define more by our data than our things, do our things matter at all?

I think ze was confused -- in favor of genderless pronouns

You've probably heard the following:


               At first I didn't want to get an X but now that I have it, I can't imagine life without one.

X could be telegraph, radio, TV, color TV, VCR, CD player, streaming, Netflix, Amazon prime, an uber account, Washer and Dryer, Car Phones (remember those), Cell Phones. If you go back in history  wrist watches or sun dials (or wrist-sun-dials!).

This has happened to me recently though not with an object. I read an article someplace saying that ze can be used instead of he or she. It was referring to nonbinaries (using `they' never quite sounded right) but actually it would be great if this was a general genderless pronoun. I am not making a political statement here (although I doubt I have any readers who are against genderless pronouns).

Once I came across the term ze I found places to use it and now I can't imagine not using it.

In a recent article I wrote I needed to say that someone was probably confused, but I did not know their gender. I used

                                                         Ze was probably confused

which is much better than

                                                         S/he was probably confused

                                                         He or she was probably confused

                                                         The student was probably confused

                                                         They were probably confused.

Note that the first two leave out nonbinaries.

0) In the article I put in a footnote saying what ze meant. In the future I may not have to.

1) Will ze catch on? This blog post is an attempt to hasten the practice.

2) Is there a term for his/her that is non-gendered? If not then maybe zer.

3) Will there be political pushback on this usage? If its phrased as a way to include nonbinaries than unfortunately yes. If its phrased as above as when you don't know the gender, what do you do, then no.

4) Is  nonbinary the correct term? If not then please politely correct me in the comments.

5) Has Ms replaced Miss and Mrs?

I have used the term ze several times since then- often when I get email from a student such that I can't tell from the first name what their gender is, and I need to forward the email, such as

                   Ze wants to take honors discrete math but does not have the prerequisite, but
                   since ze placed in the top five in the math olympiad, we'll let zer take it.

An Immerman-Szelepcsényi Story

As a grad student in the late 80's I had the opportunity to witness many great and often surprising theorems in computational complexity. Let me tell you about one of them, the Immerman-Szelepcsényi result that nondeterministic space is closed under complement. I wish I had the original emails for this story but instead I'm working from memory and apologies if I get some of the details wrong. I'm expanding from a short version from the early days of this blog.

I started my graduate work at UC Berkeley in 1985 and then moved to MIT in the summer of '86, following my advisor Michael Sipser. In the summer of 1987, Neil Immerman, then at Yale, proved his famous result building on his work in descriptive complexity In those days you didn't email papers, he made copies and sent them by US postal mail to several major researchers in complexity including Sipser. But Sipser was away for the summer, I believe in Russia, and the paper sat in his office.

Immerman also sent the paper to a Berkeley professor, probably Manuel Blum, who gave it to one of his students who decided to speak about the result in a student-led seminar. I forgot who was the student, maybe Moni Naor. I was still on the Berkeley email list so I got the talk announcement and went into complexity ecstasy over the news. I asked Moni (or whomever was giving the talk) if he could tell me details and he sent me a nice write-up of the proof. Given the importance of the result, I sent the proof write-up out to the MIT theory email list.

Guess who was on the MIT theory list? Neil Immerman. Neil wrote back with his own explanation of the proof. Neil explained how it came out of descriptive complexity but as a pure write-up of a proof of the theorem, Moni did an excellent job.

We found out about Robert Szelepcsényi when his paper showed up a few months later in the Bulletin of the European Association for Theoretical Computer Science. Szelepcsényi came to the problem from formal languages, whether context-sensitive languages (nondeterministic linear space) was closed under complement. Szelepcsényi, an undergrad in Slovakia at the time, heard about the problem in a class he took. Szelepcsényi's proof was very similar to Immerman. Szelepcsényi's paper took longer to get to US researchers but likely was proven and written about the same time as Immerman.

Even though both papers were published separately we refer to the result as Immerman-Szelepcsényi and is now just some old important theorem you see in introductory theory classes.

Don't know Football but still want bet on the Superb Owl?

(Superb Owl is not a typo. I've heard (and it could be wrong) that the  NFL guards their copyright so you can't even say `Buy Beer here for the YOU KNOW WHATl' but instead `Buy Beer here for the big game''. Stephen Colbert a long time ago go around this by calling the game Superb Owl.)

If I knew more about football  I might place a bet related to the Superb Owl. What kind of bets can I place?

1) Bet the point spread: Last time I looked the Patriots were a 2.5 point favorite. So either bet that Patriots will win by more than  2.5 or the Rams will lose by less than 2.5 or just win.

2) Over-Under: bet that either the total score will be over 56.5 or under it.

 There are prop-bets-- bets that are ABOUT the game but not related to the final score.

I've seen the following

1) Tom Brady will retire after the game. I wonder if Tom Brady (or a friend of his) could bet on this one knowing some inside information. Not i any state in America, but off-shore...

2) Jamie White will score the first touchdown.

3) Will Gladys Knight's   National Anthem go longer than 1 minute, 50 seconds (it was 1:47 seconds a few days ago but it shifted to 1:50).

Amazingly, this last one is what Josh Hermsmeyer (on Nate Silver's Webpage)  chose to focus on: here. Note that:

1) The people who picked 1 minute 50 seconds as the over-under probably didn't do much research. They might have set it to get the same number of people on both sides, which may explain the shift; however, I can't imagine this bet got that much action. Then again, I'm not that imaginative.

2) Josh DID. He did an  analysis of what is likely (he thinks it will go longer)

3) So- can Josh bet on this an clean up? Can you bet on this and clean up?

4) There is an issue: Some kinds of bets are legal in some places (betting who will WIN or beat a point-spread is legal in Las Vegas-- the Supreme court struck down a federal anti-betting rule). Some prop bets are legal. The Gladys Knight one is not.  Why not? Someone could have inside information! Gladys Knight would!

So you CAN bet  Rams+2.5 beats the Patriots LEGALLY

but to bet Gladys Knight's National Anthem will take more than 1 minute 50 seconds you might need to use  BITCOIN, and go to some offshore account. Too much sugar for a satoshi.

5) There is another issue- there is no such thing as a sure thing (I blogged on that here). People who bet on sports for a living (I know one such person and will blog about that later) play THE LONG GAME. So to say

           I will withdraw X dollars (for large X)  from my investments and bet it on 

          Gladys Knight's  Star Spangled Banner to go more than 1 minute 50 seconds

          because its a sure thing

Would be... a very bad idea.

The above was all written the day before Superb Owl. Now its the next day and Gladys Knight has sung the National Anthem. So who won the Gladys Knight Bowl? The answer is not as straightforward as it could be, see here.