# Computational Complexity

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

## Thursday, May 21, 2015

### An Intentional and an Unintentional teaching experiment regarding proving the number of primes is infinite.

I taught Discrete Math Honors this semester. Two of the days were cancelled entirely because of snow (the entire school was closed) and four more I couldn't make because of health issues (I'm fine now). People DID sub for me those two and DID do what I would have done. I covered some crypto which I had not done in the past.

Because of all of this I ended up not covering the proof that the primes were infinite until the last week.

INTENTIONAL EXPERIMENT: Rather than phrase it as a proof by contradiction I phrased it, as I think Euclid did, as

Given primes p1,p2,...,pn you can find a prime NOT on the list. (From this it easily follows that the primes are infinite.)

Proof: the usual one, look at p1xp2x...xpn + 1 and either its prime or it has a prime factor not on the list.

The nice thing about doing it this way is that there are EASY examples where p1xp2x...xpn+1 is NOT prime

(e.g., the list is {2,5,11} yields 2x5x11 + 1 = 111 = 3 x 37, so 3 and 37 are both not in {2,5,11})

where as if you always use the the product of the first n primes then add 1, you don't get to a non-prime until 2x3x5x7x11x13 + 1 = 30031 = 59x 509.

They understood the proof better than prior classes had, even prior honors classes.

UNINTENTIONAL: Since I did the proof at the end of the semester they ALREADY had some proof maturity, more so than had I done it (as I usually do) about 1/3 of the way through the course.

They understood the proof better than prior classes had, even prior honors classes. Hence I should proof all of the theorems the last week! :-)

But seriously, they did understand it better, but I don't know which of the two factors, or what combination caused it. Oh well.

## Monday, May 18, 2015

### Theory Jobs 2015

In the fall we list theory jobs, in the spring we see who got them. Like last year, I created a fully editable Google Spreadsheet to crowd source who is going where. Ground rules:

Edit

- I set up separate sheets for faculty, industry and postdoc/visitors.
- People should be connected to theoretical computer science, broadly defined.
- Only add jobs that you are absolutely sure have been offered and accepted. This is not the place for speculation and rumors.
- You are welcome to add yourself, or people your department has hired.

Edit

## Thursday, May 14, 2015

### Fiftieth Anniversary of the Publication of the seminal paper on Computational Complexity

Juris Hartmanis and Richard Stearns in a photo dated May 1963. The main theorem from their paper is on the board later improved by Hennie and Stearns. Photo courtesy of Richard Stearns. |

I've mentioned this paper several times in the blog before, including as a favorite theorem. Hartmanis and Stearns first formalized and truly popularized the idea of measuring time and other resources as a function the problem size, laying the foundation for virtually every paper in computational complexity and algorithms to follow.

Both Hartmanis and Stearns wrote about those early days. The main breakthroughs for their paper started in November 1962 and on December 31 Hartmanis wrote in his logbook "This was a good year," A good year indeed.

## Monday, May 11, 2015

### The law of the excluded middle of the road republicans

In the book

*Hail to the Chiefs*about the presidents, when pointing to a race between two people who had no business being president (I think it was Franklin Pierce vs Winfield Scott) wrote something like

*That's the thing about elections, someone has to win.*

*Looking at the republicans running for the nomination I can (with the help of reading many of Nate Silver's Columns) tell you why, for each one, they can't win the nomination. Note that this is not a partisan thing. But again, someone has to win. Is it possible to have the statements*

A1 can't win AND A2 can't win AND .... AND An can't win

and yet someone wins?

Here is a list of the candidates and why they can't win.

- Jeb Bush is what passes for a front runner nowadays. Has the money, does not have the party (very few endorsements), and not doing well in polls in Iowa or New Hampshire, the first two states. Possibly because he does not hate Obama enough. Its an interesting question of whether the party, the people, or the money pick the candidate. In the past its been the party and the money together, but that might be changing. CAN"T WIN: Viewed as too moderate by the people who go to Caucus's. Also some people may be put off by the family name. THOUGHT: If H CLINTON was not the likely Democratic candidate, thus making the family name thing a less of an issue in the general, I don't think he would have run at all.
- Marco Rubio. Running for president for the first time is hard. The republicans rarely nominate someone who hadn't run before (W in 2000, Ford in 1976 which is an outlier since he was prez). Perhaps the voters/party/money like someone they are familiar with OR perhaps first timers make mistakes. CAN"T WIN: Will make some mistake and some might think its not his turn since he's so young. Also, Senators have it rough since they sometimes vote for bills in funny ways, TRIVIA: The electoral college reps from state X cannot cast both the Prez and Veep vote for people both from state X. So you won't see a Bush-Rubio or Rubio-Bush ticket.
- Rick Perry. He lost in 2012 because either he was too soft on immigrants (he supported some sort of Dream Act) or because of his Whoops moment in a debate. Frankly I have sympathy on that one--- I also sometimes forget which cabinet positions I want to get rid of. He has tried to cure both of his problems by flip-flopping (or evolving) on immigration and by wearing glasses so at least he looks smart. CAN"T WIN: His past failure makes him not look that serious this time around, and he will likely have another WHOOPS moment.
- Scott Walker. Like Rubio but might be in better shape because he's a governor. Still, people in his home state are beginning to turn on him, a bad sign. He may soon have the same problem that Gov Brownback of Kansas has--- you promise to cut taxes, close loopholes, and cut spending, and that might actually be a good idea if done right, but you cut taxes , don't close loopholes, cut spending in stupid places like education, run up a big debt, destroy your states economy, and ... get re-elected. CAN"T WIN: Having not run before Walker will say something stupid. And as a gov of a moderate state I suspect some moderate things he did may be a problem for hard core republican voters.Plus his states current problems may be an issue.
- Ted Cruz. Which of these quotes did Ted Cruz really say and which did I hear in some satirical setting (as a fan of The Daily Show, The Colbert Report, John Oliver's show, The Capitol Steps, others, I lose track of where I heard what) (1)
*There was no ebola before Obamacare,*or (2)*Net neutrality is Obamacare for the internet.*I'll answer at the end of the post. He is now using Obamacare himself. . CAN"T WIN: A niche candidate with a small but loyal set of supporters. Not enough CAVEAT: Might be running to get some points of view out there like Adlai Stevenson and Barry Goldwater, though they got all the way to the nomination which I doubt he can. - Rand Paul. Interesting mathematically: an authenticity/electability tradeoff. Some people are attracted to his libertarianism, authenticity and consistency, but not enough to get him anywhere close to the nomination. So he changes some of his positions to be more mainstream but less libertarian, authentic, and consistent. Alas, those who trade their integrity for electability end up with neither. CAN"T WIN: His evolving views might lose him his base but not gain him any establishment cred. Also he has the chicken-egg problem in that even people who like him don't think he can win the general election. (Ted Cruz and others on this list may also have this problem.)
- Mike Huckabee. Won't get much support beyond his Social Conservative base. His stance on Same Sex Marriage will hurt him outside of the social conservatives, especially in 2015 (as opposed to his last run in 2008). I'm surprised he's running- he got what he wanted from his last run, a show on FOX News. CAN"T WIN: Was a moderate on some economic and immigration issues (he may also `evolve' which won't work), a conservative on social issues, is just the wrong mix for current republican primary voters. Note that many candidates are trying to avoid the Same Sex Marriage question as they know that being opposed to it will hurt them in the general. Plus some don't want to be on the wrong side of history (or as the kids say WSOH) . Politics- sometimes you're forced to have a public opinion that you disagree with and know will make you be on the WSOH , but you're stuck with it. I think Huckabee is sincere in his opposition to same sex marriage but he must surely know he's on the WSOH.
- Ben Carson. I suspect he is actually running to be a FOX News commentator. At that he might succeed. CAN"T WIN: First timer, never ran for anything, he'll be a curiosity not a candidate. Which of the following did he say:
*(1) Obama is a sociopath (2) Obamacare is like slavery*. This may even hurt him with the Republican hard core who want someone who can win. CAVEAT: is being African-American going to help or hurt? I doubt his campaign will get far enough to tell. The other candidates and the debate panelists (in the sanctioned debates) will treat him with kid gloves to avoid being called racist. - Carly Fiorina. She said that our founding fathers did not intend there to be a political class, what we now call politicians. They intended for ordinary people (like the president of HP), for the good of their community, to serve in office. She left out that the founding fathers also did not intend for women to be president. CAN"T WIN: First timer, never ran for anything. (correction added later: She ran for Senator of Califorina. She got the nomination but lost to Incumbent Barbara Boxer.) CAVEAT: is being female going to help or hurt? I doubt her campaign will get far enough to tell. The other candidates and debate panelists (in the sanctioned debates) will treat her with kid gloves to avoid being called sexist. HER HOOK: She claims that as a women she can neutralize H Clinton' women-advantage in the general. Interesting that she is making an electability argument instead of a policy argument, given that she has no chance of being elected.
- Chris Christie. CAN"T WIN: Hated inside of New Jersey. Hated outside of New Jersey.
- Bobby Jindal. Once said the Republicans have to stop being the stupid party. Later said some stupid things about Muslims in America. CAN"T WIN: If he ran as the moderate sane voice who will rescue the party from itself, he might get some traction. If he runs as anything else he has too much competition. Also a first-time-runner which is hard.
- Lindsey Graham. CAN"T WIN: Has worked with democrats which should be a PRO but it's a CON.
- John Kasich. Gov of Ohio. CAN"T WIN: Not that well known. Democrats have nominated unknowns (B Clinton, B Obama) but republicans almost never do (W might count).

There may be more (Donald Trump anyone?). But my point is that it seems like nobody can win, yet someone has to. Do you know other examples where A OR B OR C has to be true, yet none of A,B,C look plausible?

I can phrase this another way:

novices can't win (e.g., Ben Carson) AND first timers can't win (e.g., Mario Rubio) AND too moderate can't win (e.g., perecption of Jeb) AND unknown can't win (e.g., John Kasich).

They all can't be right, but looking at it `first timers' is prob the weak link in my reasoning. I could replace it with `inexperienced politician'. Even so, sure looks like nobody can win.

Ted Cruz: Both of the quotes I attribute to him he really did say.

I don't know Ben Carson's original quote but he backtracked to

*Obama reminds you of a*

*psychopath,*

which is much better than saying Obama IS a psychopath . But he never said sociopath, so the quote I gave is NOT from Ben Carson.

On Obamacare he said

*its the worst thing to happen in America since slavery.*But later

opposite-of-backtracking said it was

*in a way like slavery because it robs you of your ability to control your own life.*

## Thursday, May 07, 2015

### The Virtuous Cycle

Last week we have a celebration of the new CS graduates at Georgia Tech where each graduating student says what their plans are for next year. Other than the few going to grad school, they all have great jobs but the difference I see this year is how many are staying in Atlanta. Any CS student who wants to stay in Atlanta can find a great job in Atlanta.

A large number of companies are moving their headquarters or established large facilities in the Atlanta area and the reasons they give almost always include the students and researchers at Georgia Tech. We're starting to grow a good start-up culture here as well.

Companies in Atlanta want our students and our research. That helps add to the prestige of Georgia Tech which in turn draws more companies. A virtuous cycle. A similar story is playing out in several other cities across the country and I even saw it in tiny but growing Bozeman where I visited Montana State earlier this week. Computer Science these days plays a major role if not the largest role in many of these industries.

All this growth leads to challenges such as finding the people and resources to meet the growing demands. All told though a good problem to have.

We don't want the success of the STEM fields to come at the expense of the rest of academics. It shouldn't have to be CS vs Classics, Physics or Philosophy. How we make it all successful will be the great challenge in higher education in the years to come.

All this growth leads to challenges such as finding the people and resources to meet the growing demands. All told though a good problem to have.

We don't want the success of the STEM fields to come at the expense of the rest of academics. It shouldn't have to be CS vs Classics, Physics or Philosophy. How we make it all successful will be the great challenge in higher education in the years to come.

## Monday, May 04, 2015

### Sizes of DFAs, NFAs, DPDAs, UCFG, CFGs, CSLs.

If A is a decider (e.g, DFA) or generator (e.g., CFG) then L(A) is the language that it decides or generates.

The following are well known:

L(DFA) = L(NDFA) ⊂ L(DPDA) ⊂ L(PDA) ⊂ L(CSL).

We are concerned with the

*size*of these devices. For a DFA and NDFA the size is

the number of states, for a DPDA, PDA the size is the sum of the stack alphabet and the number of states, and for CSL its the number of nonterminals.

If D and E are two classes of devices (e.g., DFAs and DPDAs) then

*a bounding function for (D,E)*is a function f such that if L is recognized by both a D-device and an E-device, and L is recognized by an E-device of size n, then it is recognized by a D-device of size ≤ f(n). We abbreviate b-fun

Readers of this column likely know that f(n)=2^n is a b-fun for (DFA,NFA) and prob know that this is tight. Below are some results that I suspect many readers don't know. Some of them may be suitable for inclusion in an undergrad theory class. In what is below ≤ means Turing-Less-Than-Or-Equal.

- Stearns showed that f(n) = n^{n^{n^{O(n)}}} is a b-fun for (DFA,DPDA).
- Valiant improved this to double exp for a b-fun for (DFA,DPDA).
- Meyer and Fischer showed the 2^n lower bound for (DFA,NDFA). They also showed a lower bound of 2^{2^{O(n)}} for (DFA,DPDA). I think the question of closing the gap between Valiant's result and the Meyer-Fischer result is still open; however, if you know a ref please leave a comment.
- Valiant showed that the if f is a b-fun for (DPDA,UCFG) then HALT ≤ f.
- Schmidt showed that if f is a b-fun for (UCFG,CFG) then HALT ≤ f.
- Hartmanis showed that if f is a b-fun for (DPDA,PDA) then HALT ≤ f
- Hay showed that if f is a b-fun for (DPDA,PDA) then f is NOT computable-in-HALT.
- Beigel and Gasarch prove a general theorem from which they obtain the following: (a) if f is a b-fun for (DPDA,PDA) then f ≤_INF. (It is easy to show that there exists a b-fun f ≤ INF for (DPDA,PDA) so the Turing degree is now precise), and (b) if f is a b-fun for (PDA,CSL) then SAME AS PART (a).

*If f ≤ HALT then there exists infinitely many n such that there exists L_n such that (a) L_n is DPDA, (b) there is a PDA for L_n of size n, (c) any DPDA for L_n is of size at least f(n).*

*Are there any ``for almost all n '' type bounds? There are but they are much weaker. The following theorems are from the Beigel-Gasarch paper pointed to above.*

- For almost all n there exists a cofinite (hence DPDA) L_n that has a PDA of size O(n) but any DPDA for it has size 2^2^{n^{Î©(1)}}.
- Same as point 1 but for PDA,CSL.

Both results 1,2 above use natural languages in that they are not created for the sole purpose of proving the theorem, no diagonalization (my spell check says thats spelled wrong but I think its spelled right). Using a construction Beigel-Gasarch obtained (Meyer probably had the result 40 years earlier with a diff proof, see the Beigel-Gasarch paper for historical details) that if f ≤ HALT then for almost all n there is a lang L_n such that L_n has a CSL of size n but any PDA for it is of size at least f(n).

## Wednesday, April 29, 2015

### Is Logarithmic Space Closed Under Kleene Star?

A Georgia Tech student asked the title question in an introductory theory course. The instructor asked his TA, the TA asked me and I asked the oracle of all things log space, Eric Allender. Eric didn't disappoint and pointed me to Burkhard Monien’s 1975 theorem

Kleene star comes up in regular expressions but also makes for many a good homework problem.

Consider the following NL-complete problem: The set of triples (G,s,t) such that G is a directed graph with a restriction that all edges (i,j) have i<j and there is a path from node s to node t.

Define the following language

Allender, Arvind and Mahajan give some generalizations to log-space counting classes and also notes that there are languages computable in AC

L is closed under Kleene star if and only if L = NL.L here is the set of problems solved in deterministic O(log n) space and NL is the nondeterministic counterpart. For a set of strings A, Kleene star, denoted A

^{*}is the set of all finite concatenations of strings of A. For example if A = {00,1} then A^{*}= {Îµ, 1, 00, 11, 001, 100, 111, 0000, 0011, 1100, …} where Îµ is the zero-length string.Kleene star comes up in regular expressions but also makes for many a good homework problem.

- Show that if A is in NL then A
^{*}is also in NL. - Show that if A is in P then A
^{*}is also in P. - Show that if A is c.e. (recognizable) then A
^{*}is also c.e.

Consider the following NL-complete problem: The set of triples (G,s,t) such that G is a directed graph with a restriction that all edges (i,j) have i<j and there is a path from node s to node t.

Define the following language

B = {G#i+1#G#i+2#...#G#j# | there is an edge (i,j) in G}B is computable in log space and the string G#s+1#G#s+2#…#G#t# is in B

^{*}if and only if there is a path from node s to node t. QEDAllender, Arvind and Mahajan give some generalizations to log-space counting classes and also notes that there are languages computable in AC

^{0}(constant-depth circuits) whose Kleene star is NL-complete. B above is one such set.## Monday, April 27, 2015

### Advice on running a theory day

Last semester I ran a THEORY DAY AT UMCP. Below I have ADVICE for people running theory days. Some I did, some I didn't do but wish I did, and some are just questions you need to ask yourself.

1) Picking the day- I had two external speakers (Avrim Blum and Sanjeev Arrora) so I was able to ask THEM what day was good for THEM. Another way is to pick the DAY first and then asking for speakers.

2) Number of external speakers- We had two, and the rest were internal. The external speakers had hour-long talks, the internal had 20-minute talks. This worked well; however, one can have more or even all external speakers.

3) Whoever is paying for it should be told of it towards the beginning of the process.

4) Lunch- catered or out? I recommend catered if you can afford it since good time for people to all talk. See next point.

5) If its catered you need a head count so you need people to register. The number you get may be off- you may want to ask when they register if they want lunch. Then add ten percent.

6) Tell the guest speakers what time is good for them to arrive before they make plans so you can coordinate their dinner the previous night.

7) If have the money and energy do name tags ahead of time. If not then just have some sticky tags and a magic marker.

8) Guest speakers- getting them FROM Amtrak or Airport to dinner/hotel --- give them a personal lift (they may be new to the city and a bit lost). Getting them from the event back TO the airport or amtrak, can call airline limo and taxi. (though if can give a ride, that's of course good.)

9) Pick a day early and stick with it. NO day is perfect, so if someone can't make it, or there is a faculty meeting that day, then don't worry about it.

10) Have website, speakers, all set at least a month ahead of time. Advertise on theory-local email lists, blogs you have access to, and analogs of theory-local for other places (I did NY, NJ, PA). Also email people to spread the word.

11) Advertise to ugrads. Students are the future!

12) If you are the organizer you might not want to give a talk since you'll be too busy doing other things.

13) Well established regular theory days (e.g., NY theory day) can ignore some of the above as they already have things running pretty well.

1) Picking the day- I had two external speakers (Avrim Blum and Sanjeev Arrora) so I was able to ask THEM what day was good for THEM. Another way is to pick the DAY first and then asking for speakers.

2) Number of external speakers- We had two, and the rest were internal. The external speakers had hour-long talks, the internal had 20-minute talks. This worked well; however, one can have more or even all external speakers.

3) Whoever is paying for it should be told of it towards the beginning of the process.

4) Lunch- catered or out? I recommend catered if you can afford it since good time for people to all talk. See next point.

5) If its catered you need a head count so you need people to register. The number you get may be off- you may want to ask when they register if they want lunch. Then add ten percent.

6) Tell the guest speakers what time is good for them to arrive before they make plans so you can coordinate their dinner the previous night.

7) If have the money and energy do name tags ahead of time. If not then just have some sticky tags and a magic marker.

8) Guest speakers- getting them FROM Amtrak or Airport to dinner/hotel --- give them a personal lift (they may be new to the city and a bit lost). Getting them from the event back TO the airport or amtrak, can call airline limo and taxi. (though if can give a ride, that's of course good.)

9) Pick a day early and stick with it. NO day is perfect, so if someone can't make it, or there is a faculty meeting that day, then don't worry about it.

10) Have website, speakers, all set at least a month ahead of time. Advertise on theory-local email lists, blogs you have access to, and analogs of theory-local for other places (I did NY, NJ, PA). Also email people to spread the word.

11) Advertise to ugrads. Students are the future!

12) If you are the organizer you might not want to give a talk since you'll be too busy doing other things.

13) Well established regular theory days (e.g., NY theory day) can ignore some of the above as they already have things running pretty well.

Subscribe to:
Posts (Atom)