Sharp P and the issue of `natural problems'

 #P was defined by Valiant as a way to pin down that the PERMANENT of a matrix is hard to compute.

The definition I give is equivalent to the one Valiant gave.

g is in #P if there exists p a poly and B in P such that

g(x) = | { y : |y| = p(|x|) and (x,y) \in B } |

A function f is #P-complete if g is in #P and for all g in #P,  f is poly-Turing reducible to g.

#SAT is the function that, given a formula, returns the number of satisfying assignments. It is #P-complete by looking at the proof the Cook-Levin Theorem. The reduction of f to #SAT only makes one query to #SAT. A common way to show that #A is #P-complete is to show that SAT \le A with a reduction that preserves the number of solutions. 

Valiant proved that PERM was #P-complete (his reduction only used 1 call to PERM).

There are problems in P whose #-version is #-P complete: Matching and DNF-SAT are two of them.

Notice that I defined #SAT directly, not in terms of a poly p and a set B as above. Here is why: if you use poly p and set B one can do obnoxious things like: 

SAT = { phi : exists yz 2n-bits long such that phi(y)=T and z is prime }

The # version of this definition is not really what I want (though I am sure its #P-complete).

Valiant (see here and here) and Simon (see here) showed that  for many known NPC-problems A, #A is #P-complete. They meant NATURAL problems. Is it true for all natural NP-complete problems?

Unfortunately the statement `All NATURAL NPC problems give rise to #P-complete functions' is hard (impossible?) to state rigorously and hence hard (impossible?) to prove. 

1) Is there a natural A in NP such that #A is NOT #P-complete (under assumptions)?

2) Are there any theorems that show a large set of NPC problems have #P counterparts? Or are we doomed to, when we want to show some #A is #P-complete, come up with a new proof?

3) Can one PROVE there are NPC problems A such that #A is NOT #P-complete? (under assumptions).

Mathematics is not commutative

In my poll of P vs NP and other issues, one of the questions was


                             Is factoring in P?

One of the most interesting answers was


                             I don't really see why it shouldn't be. - Peter Shor

Recall that Peter Shor proved Factoring is in Quantum-P which lead to intense interest in Quantum Computing.

1) What if factoring was in P and this was shown before Shor's algorithm? Would Shor or someone else have ever proven factoring in quantum P? Would there be as much intense interest in quantum computing as there is now? Perhaps by physicists more than CS people?

2) What if factoring was in P and this was shown before RSA? Where would crypto be now? Zip drives with a googleplex random (or nearly random) bits and more 1-time pads? More lattice based crypto? Or RSA but with larger numbers? This may depend on how good the factoring algorithm is.

3) More generally, how much does the order of events matter for science?

a) If the Banach-Tarski paradox was discovered early on, would we have just tossed out the Axiom of Choice before so much more was build on it? Darling thinks we should toss out AC NOW because of Banach-Tarski.

b) In the model of set theory L you can do ALL of math except some parts of set theory and maybe a few other things (note quite: Harvey Friedman has found some combinatorial statements that need large cardinals to prove). Had L been discovered earlier then could we all now be working in L (except a few people who look at other models, but they are not in the mainstream)? We might know more about L and less about forcing. We would KNOW that AC and CH are true. Or we would think we know.

c) If  Engineers were the first ones to look at SAT and reductions, might they have been content to know that  if SAT \le A then A is probably hard? No need for the Cook-Levin Theorem! And then when someone proved Cook-Levin would the Engineers not really cares since they already knew SAT was hard?

d) I can imagine Ramsey's Theorem being discovered much later for some application, or perhaps never being discovered at all.

e) VDW's theorem has so few application, I can imagine it never being discovered. 

4) There are cases where if A was discovered before B then B has an easy proof, whereas if B was discovered before A, then B has a hard proof. I'll give one example:

Given HALT is undecidable, Godel's theorem is easy.

Assume HALT is undecidable. 

Let STAT(e) be the statement M_e(0) does not  halt.

There is some e such that M_e(0) does not halt  but ZFC cannot prove this.

PROOF: Assume, By Way of Contradiction that for all e such that M_e(0) does not halt,

ZFC could prove this. Then HALT is DECIDABLE:

Given e, run M_e(0) and at the same time enumerate all proofs in ZFC. It is guaranteed that

you will either find M_e(0) halts or a proof that M_e(0) does not halt. Hence you will,

in finite time, know if M_e(0) halts OR NOT.

END OF PROOF

Is the sequence of events where HALT is proven undecidable  before Godel's theorem plausible.

I  think so

I INVITE my readers to give there own examples of when Math is not commutative- meaning that

the order of events matters.

Simons Institute Gets Another Decade

 Great news out of the Simons Institute.

The Simons Foundation has ensured a second decade of research and innovation for the Simons Institute for the Theory of Computing, based at UC Berkeley, through a $35.5 million grant. The grant, which will begin in 2022, after the conclusion of the Simons Institute's first 10 years, will support the Simons Institute's mission and activities through June 2032.

Congrats to Shafi Goldwasser and her team and of course a special thanks to Jim Simons and his foundation for their support for the theory community. 

Time flies. I remember when I was on Team Chicago in the final rounds back in 2011. We lost but the theory community won as Berkeley did the institute well with amazing collaborative spaces, thanks mainly I hear from Alistair Sinclair, and the strong programs and workshops organized by the many volunteers across the theory community. 

The institute started right when I started as a department chair so I never had the opportunity for the true Simons experience, joining for a semester-long program. When I did sneak away for a week at Simons I purposely avoided the workshops for Simons is at its best when strong researchers, connected by one of the programs, just talk, work and socialize together. I joined an amazing collection of complexity theorists to form a rather mediocre pub trivia team.

Even if you never make it there, the institute has a great collection of videos of its workshops, talks and celebrations. COVID-19 has driven Simons on-line but that just opens up their workshops and other events to a wider audience.

Congrats again to the Simons Institute for what it's given to the theory community and to its next dozen years with hopefully many more to follow!

Random Thoughts on the Pandemic

 

1) Contrast the following two points and, if you have an intelligent way to fill-in-the-blank for the second one, please comment.

a) When Trump says `open the schools or I will cut of funding' I disagree, or at least he should talk more about how to do it carefully BUT there is an underlying important and serious issue: how to balance health and education. Similar for when he talks about opening up business's - how to balance heath and the economy.

b) When Trump says `hydroxychloroquine is a potential cure for covid' I (and most of the medical community) disagree, BUT FILL IN THE BLANK. Is there SOME serious issue involved here that I am just missing?

2) I have seen several approaches to large gathering, say Churchs, beach parties, motorcycle meeting etc. 

a) DO IT ONLINE.  UMCP classes will be on-line in the fall. My church has been online since mid March and seems like it will do the same in the fall. (Note- Choir is much worse than normal talking for spreading it, so Choir might not resume for a much longer time than Church).

b) HAVE THEM but SOCIAL DISTANCE and MASKS and other precautions. And it works. I hope it works.

c) HAVE THEM, realize that there IS an issue, TRY to do some of the precautions, but fail. This may be what has happened at some high schools, see Here.

d) HAVE THEM and ignore ALL precautions either because 

i) God will protect you

ii) The Government is not my boss. Such people are usually pro-business so they should NOT mind if a business on its own requires masks and SHOULD mind if its the government. I have not seen them making that distinction. Such people are usually against Federalism and for localism. So they should be upset when a Prez or a Gov overides a Mayor's Mask Mandate. I have not seen this.

iii) The whole think is a Hoax. How can people still believe this?

These three may overlap.

3) The Sturgis Motorcycle Rally in South Dakota seems to believe ii and iii. Can someone give any rational reason why they want to have this rally and why its allowed to happen. Given how many people come (usually 250,000- less now?) from all across the country, this could make thinks far far worse. But see next point.

4) Libertarians think that there is too much Government in our lives. This is a fair point of view but it needs to be tested on a case by case basis. There are some things that REQUIRE a more national response. When this happens Libertarians have two choices:

a) Apply their thinking to figure out how Gov can help with the least damage. For example, Carbon tax for global warning. In the current pandemic they might have LOCAL govs pass mandatory mask laws.. Or they would at least set a good example by wearing masks themselves. Perhaps relax regulations on medical stuff so that companies can work together without worrying about anti-trust, and perhaps look more carefully at regulations that get in the way (might be a good idea anyway).

b) Deny its a problem. Man made Global Warming is a myth. Covid is a hoax. Hence its okay to have the Motorcycle Rally. But the problem is, this doesn't just harm the people showing up, it harms others as well.

5) Early on I was puzzled that Trump didn't care more since older people (his base!) are at more risk. Did he think it would only affect democrats (early on NY was hit badly). Why didn't his advisors tell him that it would kill his own base?I ASK NON-RHETORICALLY  Or did they and he didn't list. My point is, for purely selfish reasons Trump should have taken more action earlier, so I am surprised he did not. See next point.

6) Trump could have even taken action in a Trumpian way:

The Chinese and the Democrats are waging a bio-war on real Americans (white rural older) !!! We will STOP them in their tracks and show them they can't mess with us!!  I will LOCKDOWN some cities AND provide online stuff to schools, business's (my cronies)  and churchs (SCREW that stupid sep of church and state- that was only one passage in a letter Thomas Jefferson wrote).  

He might have even got Democrats to complain that it will choke the economy and hurt the poor, and that giving stuff to churchs is against the constitution (it prob is). 

7) If a vax for covid is found, will Trump urge his base (some of whom are anti-vax) to take it? Having said that, if it comes out in October it may be untested so I doubt I will take it. I'll wait until Dr Fauci says its okay to take it. (See here for a nice song about Dr. Fauci.)

8) Some people who thought it was a Hoax and then got a bad case of it are saying loudly `I WAS WRONG! Its Real!'  I wonder if Herman Cain realized it was real before he died of it? I wish he had said `I WAS WRONG! ITS REAL! Wear a MASK' (The Whitehouse denies that he got Covid from the Tulsa Rally, here is headline only since something is behind paywalls: here)

9) At Tulsa the presidents people took DOWN signs about safe distancing. So again, why does the Prez want to kill his own base? I ask non rhetorically. I am serious- I want someone to defend his actions intelligently both this one and the hydro-whatever in the first point.

10) Authoritarian governments often claim that they bring order and can act fast to get things done. So they SHOULD have an advantage during the pandemic since they can more easily ORDER a lockdown. Yet they don't seem to be doing better.  

Russia: See Here, number of cases going up fast.

Iran: See here and Here, number of cases going up fast.

These countries and others, and America, had their leaders LIE about the extend of the virus early on. What is the upside of doing this?  I ask non-rhetorically. 

Do Senators have an Advantage for being Dem VP Nominee?

This is a non-partisan post. Even so:  I plan to vote for Joe Biden.

(Lance says that whenever I write `this is a non-partisan post'  its partisan anyway.)

I've had posts on predicting VPs before:

In this post I looked at a Nate Silver column a few months ago where they were trying to predict the democratic VP nomination before the Prez nominee was known. Some of what they said seems relevant.

In this post I PREDICTED that bets on INTRADE would not do well on picking VPs since VP picks are hard to predict and often are not from anyone's short list. I DID NOT PREDICT that INTRADE would go out of business.

I came across a statistic recently that seems relevant and inspired this post. Actually this post asks IS this statistic relevant?

From Prez candidate  Harry Truman to Prez candidate Hillary Clinton there have been 15 Dem VP nominees (not  counting incumbents) of which 13 have been Senators:

Harry Truman(Prez)-Alben Barkely. Sen from Kentucky

Adlai Stevenson(Gov-Illinois) -John Sparkman. Sen from Alabama

Adlai Stevenson(Gov-Illinois)-Estes Kefauver, Sen from Tennessee 

John F Kennedy(Sen-Mass)-Lyndon B Johnson, Sen from Texas

Lyndon B Johnson(Prez)-Hubert Humphrey,Sen from Minnesoda

Hubert Humphrey(VP)-Ed Muskie, Sen from Maine

George McGovern Sen-South Dakota)-Sgt Shriver Amb to France, Office of Econ Activity

Jimmy Carter(Gov Georgia)-Walter Mondale- Senator from Minnesota

Walter Mondale(Senator Minnesota)-Geraldine Ferraro Congressperson- NY

Mike Dukakis (Gov Mass), Lloyd Benson-Sen Texas

Bill Clinton(Gov Arkansas), Al Gore Sen from Tennesee

Al Gore (VP), Joe Lieberman Senator from Conn

John Kerry (Sen-Mass), John Edwards Sen from NC

Barack Obama (Sen-Illinois), Joe Biden Sen from Del

Hillary Clinton (Sen-NY), Tim Kaine- Sen Virginia

Of the 15 Dem VP nominees, 13 are Senators

Of the 13 Rep VP nominees, 4 are Senators  see here

My Speculations: 

1)  When a gov runs he wants someone with fed experience. That explains 5 of the cases above.

2) Senators tend to be better known than other politicians, so perhaps being well known is what you need. Note on the Republican Side Paul Ryan was a House member but was well known.

3) Why do the Reps and Dems differ on this? Is the sample size too small to make this question interesting? 

So here is the question: When trying to predict who the Dem VP will be (this year or any year) should being a Senator give someone a plus? A higher weight in a Neural Net? 

Kamala Harris is the favorite on the betting markets.  Is this because she is a Senator?

She has a national profile and has already been vetted since she rana serious campaign  for Prez in the primaries. So I would say that THATS the reason (and other reasons), not that she is a Senator. But would she have been able to run a serious campaign  in the primaries if she wasn't already a Senator? I ask non rhetorically.

ADDED LATER- one of the comments inspired me to also include who the Republicans picked for VP since Truman. Much more variety in the jobs they held prior. This is neither good or bad.

Thomas Dewey (Gov-NY), Earl Warren (Gov-California)

Dwight Eisenhower (General), Richard Nixon (Sen-California)

Richard Nixon (VP), Henry Cabot Lodge (Sen-Mass, Amb-UN)

Barry Goldwater (Sen-Arizona), William Miller (Representive-NY)

Richard Nixon (VP), Spiro Agnew (Gov-MD)

Gerald Ford (Prez, Senator-Michigan), Bob Dole (Senator-Kansas)

Ronald Reagan (Gov California), George Bush (Dir of CIA)

George Bush (VP), Dan Quayle (Sen-Indiana)

Bob Dole (Sen-Kansas), Jack Kemp (Representiative-NY)

George W Bush (Gov-Texas), Dick Cheney (Cabinet)

John McCain (Sen-Arizona), Sarah Palin (Gov-Alaska)

Mitt Romney (Gov-Mass), Paul Ryan (Represenative-NY)

Donald Trump (Businessman-NY), Mike Pence (Gov-Indiana)

The Gauss story is false yet we still tell it. Should we?

When teaching discrete math a while back I told the following story which some had already heard in High School: 

When Gauss was in 1st grade the class was being bad. So the teacher made them sit down and add up the numbers from 1 to 100. Gauss did it in 2 minutes by noting that if S was the answer then 

2S = (100+1) +(99+2) + ... + (1 + 100) = 100*101

So S = 50*101.  Then he went to Google and typed in 50*101 for the answer.

The class laughed because of course the last part about Google was false. But I then told them that the entire story was false and showed them the following slides:  here  Take a look at them (there are only 4 of them) before reading on.

(ADDED LATER: here is an article by Brian Hayes that documents the history of the story.

http://bit-player.org/wp-content/extras/bph-publications/AmSci-2006-05-Hayes-Gauss.pdf

)


So I told them the Gauss Story was false (I am right about this) and then told them a lie- that the story's progression over time was orderly. I then told them that that was false (hmmm- actually I might not of, oh well).

One of my students emailed me this semester

Dr Gasarch- one of my Math professors is telling the Gauss story as if its true! You should make a public service announcement and tell people its false!

I do not think this is needed. I also don't know how one goes about making a public service announcement  I also  suspect the teacher knew it was false but told it anyway.

OKAY- what do you do if you have a nice story that has some good MATH in it but  its not true?

Options:

Tell it and let the students think its true.

Tell it and debunk it.

Tell it and debunk it and tell another myth

Tell it and debunk it and tell another myth and then debunk that

Ask your readers what they would do. Which I do now: What do you do?