The US might die, but P and PSPACE are forever
Today, I interrupt the news of the rapid disintegration of the United States of America, on every possible front at once (medical, economic, social…), to bring you something far more important: a long-planned two-hour podcast, where theoretical physicist and longtime friend-of-the-blog Sean Carroll interviews yours truly about complexity theory! Here’s Sean’s description of this historic event:
There are some problems for which it’s very hard to find the answer, but very easy to check the answer if someone gives it to you. At least, we think there are such problems; whether or not they really exist is the famous P vs NP problem, and actually proving it will win you a million dollars. This kind of question falls under the rubric of “computational complexity theory,” which formalizes how hard it is to computationally attack a well-posed problem. Scott Aaronson is one of the world’s leading thinkers in computational complexity, especially the wrinkles that enter once we consider quantum computers as well as classical ones. We talk about how we quantify complexity, and how that relates to ideas as disparate as creativity, knowledge vs. proof, and what all this has to do with black holes and quantum gravity.
So, OK, I guess I should also comment on the national disintegration thing. As someone who was once himself the victim of a crazy police overreaction (albeit, trivial compared to what African-Americans regularly deal with), I was moved by the scenes of police chiefs in several American towns taking off their helmets and joining protesters to cheers. Not only is that a deeply moral thing to do, but it serves a practical purpose of quickly defusing the protests. Right now, of course, is an even worse time than usual for chaos in the streets, with a lethal virus still spreading that doesn’t care whether people are congregating for good or for ill. If rational discussion of policy still matters, I support the current push to end the “qualified immunity” doctrine, end the provision of military training and equipment to police, and generally spur the nation’s police to rein in their psychopath minority.
Follow
Comment #1 June 1st, 2020 at 2:41 pm
Military training? Are police getting military training? Equipment, yes, and that’s a problem, but everything I hear about the military is that the sort of problems we see with the US police forces happen less often in the military (although they very clearly still happen) due to the much more serious training they get… is that mistaken? Of course, that sort of thing doesn’t come quickly or cheaply, and we shouldn’t do that on account of police are not military and should not act like they are, but you get my point.
Note that ending qualified immunity, while a good start, is not nearly enough to fix the broken feedback loop that lets cops commit crimes without consequences. (One part of the feedback loop I have no idea how we fix is juries; a lot of the country are just authoritarians who endorse police doing this sort of thing, unfortunately, so even when you get past every other problem, you encounter the problem of the jury.)
There are various other good mitigations for police violence that people have suggested but it’s not like you intended to make a complete list so I’m not going to try to list them all either.
Comment #2 June 1st, 2020 at 3:02 pm
Sniffnoy #1: I meant stuff like this. For me, the fact that the Minneapolis police union defied the mayor in order to continue to offer “warrior training”, and that this happened a year ago, was crucial context for making sense of what happened with George Floyd.
It’s like: have the abusive police officers turned on the news even once in the past decade? What could possibly make them think that people still won’t pay attention or care if they kill unarmed black people in their custody? Isn’t it like a priest, in 2020, thinking no one will notice if he molests an altar boy? But if police are being explicitly trained to view everyone they interact with as a lethal threat, if they’re in a little cultural bubble where that’s normalized…
Anyway, I apologize for any unintended ambiguity.
Comment #3 June 1st, 2020 at 3:58 pm
Around the 30-minute mark while discussing P vs. PSPACE, you describe Go and Chess as being in PSPACE. (I understand you’re obviously simplifying here to talk about Generalized-Go and Generalized-Chess.) But these two aren’t great examples, as they’re at least EXP-hard. (IIRC, Chess is EXP-complete and Go is EXP-complete under certain rulesets.) The point is that these games can last exponentially many moves. So in fact, thanks to the Time Hierarchy Theorem, playing (Generalized-)Chess perfectly is a problem we know provably *isn’t* doable in polynomial time.
Comment #4 June 1st, 2020 at 4:48 pm
Yesterday I visited the murder site. The intersection has been turned into something of a shrine. People are angry and upset, but the community vibes are positive overall. There was no racial tension. The governor announced the other day that the protests are no longer about George Floyd. That is bullshit. All day protesters were chanting “WHAT’S HIS NAME? GEORGE FLOYD”. The neighborhood of the murder has not been touched by looting or arson; that is confined to the main commercial drags. There were no cops. I don’t think they will dare to show up for weeks.
I know that a lot of readers of this blog will see looting on the news and think “I support their right to protest, but this isn’t the right way to do it.” If you think that, I encourage you to watch the whole George Floyd murder video [1]. Derek Chauvin had his knee on the neck of George Floyd for eight minutes. Eight minutes! That is a really long time. And you should watch it. All of it, the whole thing. Watch Floyd say “I can’t breathe. They’re gonna kill me.” Watch the moment when Floyd goes unconscious, then watch as Chauvin keeps choking him for another four minutes. It’s hard to say exactly, but you can probably even watch the instant of Floyd’s death.
Watch the whole thing, then come back and say the protesters need to be better behaved.
If you are a white guy and you think this kind of thing is of no concern to you, watch the Daniel Shaver execution video too [2]. He was just some unarmed white guy, and a cop shot him even when he was no threat to anyone. The cop was acquitted of any wrongdoing.
People like Derek Chauvin and Bob Kroll are psychotic bullies, and they need to be stopped. Probably most readers of this blog are or have been nerds. Remember the kinds of mean bullies who would pick on you for no reason when you were a kid? This is how they turn out. They are violent, and they will kill you if they want to, and they will almost certainly get away with it.
That is what these protests are about.
[1] https://www.youtube.com/watch?v=DNX8-PWCi6E
[2] https://www.youtube.com/watch?v=WCdRL6bqSKI
Comment #5 June 1st, 2020 at 4:49 pm
Ryan #3: Good point, thanks! But when I talk about games like generalized chess or go, unless specified otherwise, I always implicitly have in mind a polynomial upper bound on the number of moves (as there would always be in “actual tournament play”…). I usually remember to say as much; extremely sorry if I neglected to in the podcast! (I haven’t listened to it 🙂 )
Comment #6 June 1st, 2020 at 5:01 pm
Sniffnoy #1:
1. The fact that the military has much clearer situations to deal with is part of the reason for less problems.
2. Obviously a problem when police have to deal with extremely violent people (Chicago’s five or ten murders a day aren’t being done by ghosts) and also protesters who are egging them on.
3. Police deal with laws all the time, and are likely to be good at using them. So it is very hard to get rid of bad cops, because they know all the legal tricks, and the union always backs them.
Comment #7 June 1st, 2020 at 6:37 pm
By the way Scott, I wanted to tell you that I have been thinking a lot about your post on common knowledge [1]. In fact, because of that post, my current short-term political goal has been to tell people I know how I feel about the issue (police brutality, not P vs NP), and also to tell them to let others know how they feel, and also to tell them that the very act of saying it can affect the world in concrete and actionable ways!
This goes beyond simple blogging (for example, this post [2]). I live in a densely populated neighborhood in Minneapolis, and I have been going out during curfew. I’m not about that riot life, so all I do is mill around the street, but still. Just being outside at those times makes it common knowledge to my neighbors that someone is out there breaking the curfew, peacefully and quietly.
[1] https://scottaaronson-production.mystagingwebsite.com/?p=2410
[2] https://nickdrozd.github.io/2020/05/30/derek-chauvin-did-this.html
Comment #8 June 1st, 2020 at 7:12 pm
@ Nick #4, you wrote:
Would you be OK with looting and ransacking taking place in your house, or is looting something you support only when it occurs in other places? If you support looting so much that you’re willing to see this stuff happen to you, in your house, than I admire your consistency and strength of conviction.
And yes, I watched the George Floyd video, as well as probably every video of police brutality associated with the riots that is possible to find on social media. Have you seen videos of looting and rioting? Random acts of violence against innocent bystanders are not OK, no matter what preceded it. Two wrongs don’t make a right.
To state the obvious–which shouldn’t need to be stated in a comment opposing looting and rioting–I’m in favor protesting, for equality of opportunity, against racial injustices, and a strong advocate for reforming our policing and penal systems. Looting and rioting won’t achieve any of those things, though they may lead to a further diminution of our civil liberties and an increasingly militarized police force.
Videos of looting:
Here are some videos of what looting is actually like:
https://www.reddit.com/r/PublicFreakout/comments/gsrjm7/black_business_owner_who_invested_life_savings/
https://www.reddit.com/r/PublicFreakout/comments/gu9smb/security_cam_view_of_husband_and_wife_attempting/
Comment #9 June 1st, 2020 at 7:37 pm
Incidentally, I very much hope that the current riots won’t lead to a civil war. If they do, though, I imagine that I’ll find myself on whichever side of the war Trump isn’t. Not because that side will be purely virtuous, but simply because Trump’s side will leave me no choice.
Comment #10 June 1st, 2020 at 8:19 pm
Regarding looting and whether it’s justified/helpful: only a small fraction of protesters are looters, and I suspect many of the looters are not there to protest at all. A lot of people I know are simultaneously saying “Looting is a useful act of protest because it’s the only way to get the message across” and “Police and white nationalists are destroying property themselves and blaming it on the protesters to discredit them”. I’m inclined toward the second story, but we need an overhaul of the police system in any event so I don’t think looters need to be a huge point of contention.
Comment #11 June 1st, 2020 at 9:06 pm
@ Nick #4 wrote:
Because a cop murdered an unarmed man, you are seriously defending or even advocating widespread theft and property destruction against random, innocent and completely unrelated business owners as a remedy? If so, why stop at looting? Why don’t you recommend people just go kill random people as retribution for George Floyd. That is truly outrageous.
Comment #12 June 1st, 2020 at 9:32 pm
Check out the debate between Philosopher J.R. Smith and a white leftest:
“Political Window Breaking: Pros and Cons”:
https://www.tmz.com/2020/05/31/j-r-smith-attack-fight-video-los-angeles-la-protests-nba/
Comment #13 June 1st, 2020 at 9:40 pm
Steve E #8
I am not in favor of looting, but it is the price we pay for the behavior of police in America. Derek Chauvin murdered George Floyd over the course of eight minutes in broad daylight in full view of witnesses with cameras. He thought he would get away with it, and that was a perfectly reasonable belief on his part. Even today, a week after the murder, the head of the Minneapolis police union declared that “due process” wasn’t followed and that Chauvin shouldn’t have been arrested at all [1].
That is truly insane, but that’s the American police system. If you live in America, you are a participant in that system, whether you want to be or not. Brutal and unwarranted police violence has been a matter of common knowledge since at least the Rodney King beating. You knew it was happening, I knew it was happening, we all did. Did you do anything about it? Black people have been protesting the whole time, but they were ignored. Colin Kaepernick got blackballed from the NFL for speaking out about exactly this. Well, their voices are being heard now, aren’t they? If someone tries talking to you and you don’t hear them, they will raise their voice.
So again, I am not in favor of looting, but what else did you think would happen? Did you think that black people were going to eat shit forever and not do anything about it?
If you’re worried about homes and businesses, blame the shitbag cop who for eight minutes thought that he would get away with murder. Blame the spineless county attorney who failed to order Derek Chauvin’s arrest in a timely manner [2], and who still hasn’t ordered the arrests of the other three cops who aided and abetted the murder. Blame yourself and me and Scott and everyone else for not doing anything about this sooner.
As long as police in America remain violent and unaccountable, this will continue to happen. Looting is an inevitable consequence of the actions of cops like Derek Chauvin.
Oh, and I watched a gas station up the block from where I live get looted and then burned. It wasn’t nearly as shocking as watching a video of a man being choked to death.
[1] https://twitter.com/ChiefHarteau/status/1267460683408564225
[2] https://minnesota.cbslocal.com/2020/05/28/we-have-to-do-this-right-hennepin-county-attorney-mike-freeman-says-george-floyd-investigation-will-take-time/
Comment #14 June 1st, 2020 at 9:45 pm
All:
Just to lighten up the mood a bit, here is an email I just got. (I am not making this up). It is from Conrad Wolfram promoting his new book showing how to teach kids computer science instead of math. This follows brother Peter’s book on how physics is just a game of Life.
I should point out that I once bought a copy of “Mathematica”, and it is great, and the book is astounding, so there is that. However Mathematica and I do not agree on the antiderivative of cosh^p(x) for non integer p. It is possible that some relation for 2F1 functions makes the solutions equivalent. I argued with a math tech at Wolfram about it and we did not agree.
Comment #15 June 1st, 2020 at 11:31 pm
@ Nick # 13, you wrote:
I’m glad that you’re now saying you’re against looting, but that’s not what you said in your earlier comment, and that’s not what I take from your blog post. Brandon #11 seems to have understood your comment the same way I did, so I think the issue isn’t my reading comprehension but rather your articulation.
If your house gets ransacked, and you get beaten up by a looter, then you blame the cop who killed George Floyd. If this happens to me then I, for one, will blame the perpetrators while keeping in mind the system that produced that behavior.
Imagine, for the sake of an interesting thought, that we weren’t talking about looting and rioting. If Alice was sexually abused by Bob as a child and goes on to rape Charlie as an adult, we blame Alice for raping Charlie, even while considering how what Bob did to Alice may have influenced what Alice did to Charlie. Likewise, if System X oppresses Looter Y, and Looter Y steals from and assaults Innocent Bystander Z, we blame Looter Y for the crime, even while we consider how what System X did to Looter Y may have influenced what Looter Y did to Innocent Bystander Z.
Comment #16 June 2nd, 2020 at 12:11 am
Raoul Ohio #6:
I’m not sure you’re correct about #1, when you consider what sorts of things the military has had to deal with in the past two decades (a lot of police-like stuff). As best as I can tell, they just have clear rules that they’re seriously trained on, that they can actually follow those rules rather than freak out and shoot people when the situation gets a little scary like cops do.
Nick #4:
That’s really not an argument. A cop murdered George Floyd, therefore rioting makes sense? It simply doesn’t follow. In your comment #13 you claim you’re not in favor of looting, but your comment #4 sure seems to contradict that, containing an attempt at a rebuttal at those who are against looting. Apologies, but this looks like you attempting to silently shift your position in response to criticism without at any point acknowledging error. Again, if I’ve misread you then my apologies, but that is what it looks like.
But, anyway, here’s the thing about rioting/looting — it’s not just ethically wrong for all the obvious reasons (you’re attacking people that are helping you rather than hurting you, you could at least focus on the police station!), it’s also tactically stupid.
I see this logic a lot, like, oh, well, of course it makes sense to riot when you’re so oppressed, it’s simply what you have to do. No it isn’t! It is actively counterproductive!
Look, despite the best efforts of Donald Trump & co., we do live in what is still basically a liberal democratic society. And the way you get your way there, is by getting people on your side so they’ll vote in favor of your demands. The fight you need to win isn’t physical, it’s social. And you don’t win social fights by committing violence.
No, if anything you win social fights by having violence committed against you. Because then people will sympathize with you and see that you’re the good guys and your opponents are the bad guys.
It’s the MLK plan or the Gandhi plan. It often gets glossed as “nonviolence”, and this leads people to dismiss it — why would nonviolence magically get us our way? We tried being nonviolent and that got us nowhere, so now we need to be violent. The thing is that this plan has gotten stuck with a misleading name. Yes it’s nonviolent, indeed that’s a key feature of it, but there is more to it than that; not everything you do is nonviolent is part of this, and the reason your previous nonviolent efforts got you nowhere is likely because they lacked the other key parts of this plan.
So like I said — you don’t win social fights by hitting people, you win social fights by them visibly hitting you. Obviously, the visible part is key here. And also a big part of it is getting them to hit you — it’s not enough to be nonviolent, you need to deliberately provoke people enough to the point that they attack you. But, and here’s the key thing, you need to do it while retaining the moral high ground. That’s where the nonviolence comes in. If you provoke an attack by yourself striking first, then you’ve lost; people will (rightly) blame you. But if you can provoke an attack on yourself while visibly refraining from anything blameworthy, then you win sympathy. And if you go further, and refrain from even fighting back once struck — because while there’s nothing blameworthy about fighting back, the unfortunate reality is that if you do people will find a way to blame you anyway — then you win mega-sympathy. You deliberately lose the physical fight but you win the social fight, and that’s how you actually accomplish things.
Really — at the risk of being patronizing — it surprises me how ill-understood this generally appears to be, given that all it should take to understand it is the ability to think more than a single step ahead.
…of course, that’s not to imply it’s easy. Actually executing this is seriously difficult because it requires serious organization and discipline to maintain the necessary level of refusal-to-fight-back. It’s not really something you can expect in a spontaneous protest like this. So, for that reason, I feel like there’s a limit to how much I can blame protesters who turn violent… but I’m not sure that applies to those who go on to attack random stores and such, rather than the police.
(Of course, it’s also worth noting that a lot of looting doesn’t seem to be being done by the protesters at all, but rather just criminal opportunists. From what I’ve read, the cops in a number of places are refusing to police in an attempt to say “See? You need us.” Hmph. We can hope not many fall for this, but given how authoritarian much of the populace is frankly I’m not optimistic…)
Comment #17 June 2nd, 2020 at 12:29 am
Sean making the point that the ‘complexity’ of complex systems theory is not the same as the ‘complexity’ of computer science. Hmm. What makes him so sure? It seems to me that there should be a way to unify all the different notions of complexity, leading me to suspect that the ‘complexity’ of computer science is just a special case of the ‘complexity’ of complex systems.
And again, regarding cosmology, if you squint really hard, is the the ‘space’ of complexity theory really that different from physical ‘space’?
And then there’s the old mystery of the metaphysical status of mathematics. I’m tending towards the view that ‘math’ and ‘physics’ are just ontological categories we use to make sense of reality, and once you take that view, it’s hard to see a clear-cut dividing line between them. Rather, I think it’s more like a continuum perhaps, where we tend to interpret things that are highly localized as ‘physical’, and things that can’t be so easily localized as ‘mathematical’. In other words, mathematics is just physics with less structure (relaxation of spatial and temporal constraints) ?
I think that the right interpretation of QM comes down to only two coherent possibilities, either many-worlds, or a hidden-variables theory where physics is geometry, and there’s some new kind of geometry underlying ordinary space-time, perhaps based on the ‘abstract space’ of complexity theory ! I’m starting to lean towards the latter view…
Comment #18 June 2nd, 2020 at 3:33 am
I really enjoyed the interview. When talking about Penrose, I personally would have at least mentioned that Hypercomputation is still very much an active area of research in Theory of Computability and Mathematical Logic, whether it’s relevant for the physical universe or not.
Comment #19 June 2nd, 2020 at 4:25 am
mjgeddes #17: If you squint hard enough, then everything is related to everything else, including computational complexity and Santa Fe Institute complexity. The point, though, is that two things are not necessarily more related just because of the historical coincidence of sharing the same word.
Comment #20 June 2nd, 2020 at 4:33 am
1Zer0 #18: My problem is, we already have a name for the study of degrees of uncomputability, divorced from connection to the physical world! That’s computability theory (what used to be called recursion theory).
If, on the other hand, one does want to talk about physics, then surely one should talk about the Bekenstein limits from quantum gravity that seem to rule out hypercomputation (do they indeed rule it out? good question!)
Much of the literature on hypercomputation strikes me as trying to have it both ways—i.e., to make claims about the “real world” that aren’t actually about the real world—by simply ignoring Feynman’s dictum that “nature isn’t classical, dammit!”
Comment #21 June 2nd, 2020 at 5:37 am
Riots represent flashpoints where a significant number of citizens have lost faith in the government and its institutions. Therefore the whole discussion then of “what is justified”, “what is looting”, “what is a crime”, and so on becomes meaningless. The law, property rights, etc are social constructs grounded in some legitimizing concept, such as The Social Contract, or Rawl’s concept of Justice. The only exception is people that believe it’s all set up by some supernatural entity, but I will ignore such superstitious nonsense. It’s become obvious of the last many years that the US police force is not fit for purpose and has little interest in legitmising itself to the American public. This has built up a lot of anger and resentment, which given a suitable trigger, spills out as rioting. If allowed to fester it will eventually lead to large parts of the US becoming ungovernable. This is how failed states are made. Rather than making dimwitted noises about whether the protesters/rioter are good or bad it would be better if people started thinking about how to make the institutions of the US legitimate again in the eyes of their citizens. Riots aren’t a political strategy, they are just all that’s left when all other political startegies have been tried and failed.
Comment #22 June 2nd, 2020 at 6:06 am
Bunsen Burner #21: I was inspired by the statement of George Floyd’s brother, which President Obama tweeted yesterday:
“Let’s do this another way. Let’s stop thinking our voice don’t matter and vote. Not just for the president…educate yourself and know who you’re voting for. And that’s how we’re going to hit ’em.”
It’s a crazy idea, but if it works, it has a lot of advantages over complete societal breakdown, rioting, and civil war.
Comment #23 June 2nd, 2020 at 8:27 am
I’m going to make what I’m sure will be a very controversial attempt to relate the two themes of this post.
I think that what we are observing in the human sphere (and have observed since the beginning of history) is inevitable in a P != NP world. Humans are the result of one form of pseudo-intelligence, the heuristic, of genetic search, which after many millions of years gave rise to a new and vastly more powerful form of pseudo-intelligence, that bag of still poorly understood heuristics implemented by the human brain, that we call neural networks.
The fundamental problem with these heuristics is that they can generate far more complexity than they can understand and control. Or, like Einstein said, “only two things are infinite, the universe and human stupidity, and I’m not sure about the former”.
Hence if you are tired of all the nonsense yet want to continue living in this world, the only true solution is to find an efficient algorithm for an NP hard problem.
Comment #24 June 2nd, 2020 at 8:31 am
Scott #9
If the situation gets anywhere near to a civil war, I hope you will leave the US. Seems wiser to me than choosing sides. People matter, not nations. Instrumentally, brilliant thinkers like you matter even more.
Comment #25 June 2nd, 2020 at 8:48 am
Scott #22
Sure, no one actually wants social breakdown and civil war. I remember an interview with a Syrian protester (now refugee) saying they didn’t want a civil war or the dissolution of Syria. Unfortunately you play the cards you’re given. Right now I do not see a political candidate in the US at either the national or local level who has the stomach for the kind of wholesale reform necessary to fix the two institutions that are at the root of your current civil strife, namely, Law Enforcement and the Justice system. Just the opposite, you have Senators calling for protesters to be shot.
Comment #26 June 2nd, 2020 at 9:03 am
@Sniffoy#16- to be fair, a lot of non violent movements only succeeded BECAUSE the regime had become less ruthless than it used to be (MLK, Eastern Europe.) In a situation like ours, of course, where we have democratic elections and a free press, violence will only repel people that will be tempted to vote Democratic.
Comment #27 June 2nd, 2020 at 9:50 am
Looking forward to listening to the podcast.
On the topic of the existential threat to democracy, I wonder if the public can put pressure on large corporations who normally like to remain apolitical. It’s hard to convince the uninformed individual, but it may be possible to convince corporate boards that Trump is an existential threat to our country and their business. If a collection of CEOs came out and vocally decided to repudiate Trump’s actions and rhetoric, that may help convince more of the voting public that he is in nobody’s interest.
Comment #28 June 2nd, 2020 at 9:52 am
wrt math and physics: Vladimir Arnold said, ‘math is the area of science where the experiments are the cheapest to carry out’. It’s always intrigued me that where he studied (under Kolmogorov)at Moscow State University is called the ‘Department of Mechanics and Mathematics’
wrt George Floyd, read the article in The Atlantic by Graeme Wood, ‘How do you kneel on a neck for nine minutes.’
Comment #29 June 2nd, 2020 at 10:00 am
I will register a prediction that the US will be fine as a nation, however things turn out. It won’t “collapse” or “die”. (This is barring a sudden, hard to predict apocalyptic event like AI uprising or meteor strike. If the US dies from nuclear war or global warming, though, then that counts as being sufficiently due to our incompetence that I would concede you had the right idea with your predictions).
Comment #30 June 2nd, 2020 at 10:08 am
I find the looting really depressing both because it tends to undermine the highly legitimate moral high ground of the protests. which I support, and because of my fear about the reaction to it.
In my area, reports are that the damage seems to have largely been the work of young white males and groups that have been doing this sort of thing on a smaller scale since the WTO protest.
At the same time I had this strange thought: the stores being looted have been sitting on merchandise that they have been unable to sell for months, some of which is seasonal. If they are insured for losses like this, which I suspect that many larger retailers are, the insurance might let them recoup more of their losses than they would otherwise.
Well at least there is some really positive news amid the rest of this depressing situation:
https://www.sciencenews.org/article/universe-missing-matter-found-fast-radio-bursts
Comment #31 June 2nd, 2020 at 10:18 am
By the way, somebody on this blog mentioned the documentary “Kill Chain”. Good recommendation. It should be required viewing because the threat of election hacking alone necessitates every sentence (including mine above) of the form “A strategy to win the election is…” to have a great big asterisk next to it.
Election hacking doesn’t seem to be a topic of conversation these days. Even a recent twenty minute segment from John Oliver on the topic of voting had no mention of it.
Comment #32 June 2nd, 2020 at 11:06 am
Gerard #23
What you’ve attempted to enunciate is quite close to the thesis that Joseph Tainter makes in his “Collapse of Complex Societies”
Comment #33 June 2nd, 2020 at 11:06 am
Sniffnoy #16,
Good point. Probably a another aspect is that soldiers in the military do not have powerful unions that largely allow them to do whatever they want. Currently in NYC, the police Union is fighting with the mayor and threatening his daughter. Unions are basically a good thing, but just with everything else, power corrupts.
Comment #34 June 2nd, 2020 at 11:19 am
I also live in the Twin Cities, and it’s hard to find the words for my dismay and disgust that our police force is still this corrupt. The phrase about “a few bad apples” goes on to say that those few “spoil the barrel.” At the very least, the rage is understandable.
On the one hand, there are similarities between the violence of burning an auto parts store and the violence of burning a cross on someone’s lawn. Both come from anger. The difference is that the former is a reaction, while the latter is an action. This matters.
Violence is never justified. But it is often the last resort of the oppressed. **WE** (in our society) too often leave them no other choice.
Back when everyone was up in arms about Colin Kirkpatrick I saw a Tweet that kinda said it all:
“Rioting and Looting: Why can’t people protest peacefully?!?!
Colin Kirkpatrick kneels peacefully: No!! Not like that!!”
What options remain?
Comment #35 June 2nd, 2020 at 11:28 am
MJGEDDIS #17.
Obviously a general enough Complexity Theory could encompass both CS Complexity and CST (Complex Systems Theory) ideas, plus any other specialization.
But a big difference is that CS Complexity is largely asymptotic in a “way out there” sense, and many other types of complexity are a little closer to the real world.
I have often tossed out a comment that does not seem to get much traction in the CS community, but I am obviously right: P = NP might be the most important problem in CS, but it is 100% irrelevant to any PRACTICAL problem, because the boundary is so “far out”. The boundary is past anything that can ever be done.
A standard argument goes like this. Person A says: “an n^100 (or, n^1000000) algorithm is useless because if every atom in the universe was a computer, …, bla bla bla”. Person B says “but usually refined analysis gets n^100 down to n^6 or so”. I say that is pretty weak. Maybe this has only been done for easy problems. There is no way to know if such a reduction is always, common, or rare.
Comment #36 June 2nd, 2020 at 11:39 am
Bunsen Burner,
You might add another dimension to your thoughts about what should happen. Laws are made by elected officials. There is a kind of goofy system of how this works, and by historic quirks if favors right wingers, who also cheat in every possible way. that is the hand we are dealt, the reality of the system. So in considering change, you have to think in terms of getting people elected who will vote for it. It’s not “a candidate who has the stomach for the kind of wholesale reform necessary”, it is getting a majority large enough to make major changes.
Comment #37 June 2nd, 2020 at 1:04 pm
In India, police is so bad that when someone is in trouble they don’t even think about calling them. If a woman walking on a lonely road feels worried about her safety (say she’s being followed in a suspicious manner by a group of men), she calls her family (as newspapers report the next day), never the police.
All the horrific rapes you hear about in India on international news begin like this – woman alone with a cell phone (and she doesn’t call the police). The police would be risky for her to call, unless she came from a well-connected rich family. They’d hurt her for sure, is how she’d perceive the situation.
To avoid this situation I’d not go out after dark except in a taxi with a trusted driver. The lack of real law and order restricts what you can do in India.
In America, if I were in her place (feeling unsafe), I would call the police without hesitation.
I can move about more freely here, even at night. It is a country with excellent law and order, by and large, is my impression. Shouldn’t significant credit for this go to the police? It is possible my perception is quite flawed. I am only one data point as well.
It is possible that I don’t understand the various complexities in American society but maybe it is just a case of identifying the bad actors who give all cops a bad name?
Comment #38 June 2nd, 2020 at 1:07 pm
Michael #26:
Yes, that’s an important caveat worth noting. There are unfortunately too many examples of that. But, as you say, the US does not fall under that caveat.
Bunsen Burner #21:
Does it require a “social contract”, or does it just require recognizing the opportunity for long-term profitable exchanges? People won’t trade with you if you make yourself known as someone who steals.
Comment #39 June 2nd, 2020 at 1:13 pm
Jon K. #31,
> Election hacking doesn’t seem to be a topic of conversation these days. Even a recent twenty minute segment from John Oliver on the topic of voting had no mention of it.
Security & elections experts have long said that mail-in voting is very insecure, and previously the media and online discourse reflected these concerns. But recently Trump agreed with them, so they’ve been forced to flip their position. Now much of the left-leaning media and online discourse avoids talking about election fraud, because it’s become a shibboleth of the political Right.
Here’s a WP piece saying this: https://www.washingtonpost.com/opinions/2020/05/28/trumps-concern-about-mail-in-ballots-is-completely-legitimate/
As an observer of US politics & culture, I think it’s a pretty stark description of how discourse sometimes behaves: “we’ve flipped on a factual issue because Trump unexpectedly agreed with us”. I dread the day when Trump (or some other figure widely reviled in our circles) will weaponize this by deliberately agreeing with a smaller group he secretly dislikes to make the majority turn on them. Imagine the fallout from Trump tweeting “Women are underrepresented in STEM because they’re not interested, #DamoreWasRight and we should look into his illegal firing”.
Comment #40 June 2nd, 2020 at 1:22 pm
Raoul Ohio #35: It’s not as if CS theorists are unaware of these possibilities! The trouble is that there will presumably never be an elegant theory of concrete instance sizes—it will just be this problem, and that algorithm, and so on forever. Whereas in the asymptotic setting, we already have large parts of an elegant explanatory theory, and it’s plausible that we could someday prove the rest of it (e.g., P≠NP), and if we did, that would have major and obvious real implications for the real world (e.g., that secure pseudorandom functions are at least possible), even though we’d obviously need additional input about the concrete instance sizes as well.
Comment #41 June 2nd, 2020 at 1:45 pm
The people who investigate crimes and arrest criminals have the most opportunities to get away with crimes. We need better systems that recognize that and guard against it. Military people usually don’t have the same responsibilities and incentives. (When they do, sometimes bad things happen in the military too.)
I go back and forth on the notion of reliable lie-detectors (involving things like MRI scans). A) if we could ask every cop at the end of a shift, “Did you break any rules or regulations or bully anybody or … today?”; and have every political candidate go through similar public interviews, etc., we might have a better shot at a just society. B) On the other hand, if Trump had that technology under his control, he would use it to enforce loyalty.
I did a bunch of dumb things that I regret as a kid. If I had known I might have to face a reliable lie-detector afterwards, I think that would have stopped a lot of them. So I’ll tentatively opt for the lie-detectors. Obviously there would have to be regulations on their use, monitored by people who were also subject to lie-detector audits.
On alternate days, I dream about wise AI judges and administors.
Comment #42 June 2nd, 2020 at 1:47 pm
Speaking of complexity classes, maybe you can help clarify the confusion here, since their claim seems impossible: https://twitter.com/FrankWilczek/status/1266412498581848064?s=20
Comment #43 June 2nd, 2020 at 1:50 pm
Daniel Armak #39: I know actual election security experts. Their position is that voting by mail is not ideal (because, e.g., it has no solution to the husband-coercing-his-wife problem), but that in the middle of a pandemic it’s by far the least bad option. And that it can be made better with extra measures, for example to let people verify that their vote was counted. I’m satisfied that they would’ve said the same thing even before Trump weighed in.
Comment #44 June 2nd, 2020 at 1:59 pm
Wyrd Smythe #34:
I’ve seen this meme going around a lot. I think it has two fundamental mistakes.
The first is assuming that Colin Kaepernick’s kneeling is the only form nonviolent protest can take. “Nonviolent” encompasses every strategy that eschews violence. One should not infer that because one nonviolent strategy doesn’t work. Again: MLK and Gandhi were very effective with their nonviolent strategies. Why? Because they actually did more than merely “not being violent”. They had a plan, of which not being violent was merely a part. I already wrote about this above in comment #16.
The second mistake is in treating the generic populace as a unified whole, and looking at the worst parts of it. No, the sort of people who were fainting over a football player daring to protest are not people you are going to convince peacefully… but they’re not people you’re going to convince violently either. You should ignore them, and focus on who you can usefully appeal to: The marginal unconvinced voter. Think about how that person will react, not how the racists and authoritarians will react. And when you consider the marginal unconvinced voter, it should be pretty clear that the use of violence makes your position worse rather than better.
Comment #45 June 2nd, 2020 at 2:08 pm
Scott #41: you’re right, and maybe my characterization of mail-in voting as “very” insecure was overblown. Although bad and least-bad are not mutually exclusive.
I do still think that the explanation of why media is now less concerned about election fraud is plausible. (Of course there might be other causes contributing to the same result.)
Comment #46 June 2nd, 2020 at 2:15 pm
Deepa #37
> In America, if I were in her place (feeling unsafe), I would call the police without hesitation.
Just 3 years ago, yet again in Minneapolis, a white woman originally from Australia called police to report a suspected sexual assault (against someone else) when they arrived they shot her dead for no reason at all.
Here the primary function of the police is supposed to be to protect and serve the citizens. That’s why Americans find such incidents so shocking.
If the police in India are as bad as you say then what is their function ? Wouldn’t it be better to get rid of them entirely and let everyone defend themselves ?
Comment #47 June 2nd, 2020 at 2:21 pm
Daniel Armak #45: Sure, I can easily believe that opinion writers suddenly become for X because Trump is against it. The thing is, while it’s true that “reversed stupidity is not intelligence,” Trump probably comes about as close as the world offers to a counterexample to that principle! In any case, of course what’s actually true is a separate question, and I’m satisfied that mail-in ballots are the least bad option under the circumstances. I hope to vote that way myself and I hope it’s feasible in as many states as possible.
Comment #48 June 2nd, 2020 at 2:34 pm
Scott #20,
Yeah, I actually first heart about the Bekenstein bound reading your (insightful!) “The Ghost in the Quantum TM” paper. I comprehend why it’s perfectly consistent with the “Discrete – Continous” Duality in QM.
Judging from my limited understanding of physics, the 2nd law of thermodynamics itself isn’t an axiom, but derived from statistical mechanics. Physicists seem to have a habit of reductionism (scalewise) and formulate axiomatic rules on microscopic scale to derive theorems regarding macroscopic scales. I suppose the Second Law of Thermodynamics, which is apparently used as assumption in the derivation of the Bekenstein bound, is one such law.
The question though, is Bekenstein’s Boundary Statement (or its assumptions like the second law of thermodynamics) still a derivable theorem in a final theory of quantum gravity?
I don’t suppose knowledge about quantum mechanics is common among all authors of hypercomputation papers. You can always just take the freedom to assert a possible world which is Newtonian down to the core – where quantum mechanics doesn’t exist. Yeah sure if the author knows better and deliberately states it as definitely possible in our little part of reality, that would be fooling the audience around.
Comment #49 June 2nd, 2020 at 2:35 pm
WCZ #42: I looked at Wilczek and co.’s paper with interest, and we briefly discussed it at our weekly UT group meeting. Long story short: based on past experience, for example with the quantum adiabatic algorithm, I’m extremely skeptical about whether the reported speedup (which they tested on simulations of up to only 20 qubits) will scale to the asymptotic regime. But it’s a serious proposal that needs further study (and will surely get it); it can’t be dismissed out of hand.
In any case, it’s crucial to understand that, even if this stands, it doesn’t mean that NP⊆BQP or anything like that, since it’s only for random instances of Max Independent Set, not worst-case instances. But as far as I know, it would be the first example of its kind, where you’d get a superpolynomial quantum speedup on natural random instances of an NP-hard approximation problem (for a fixed approximation ratio).
Comment #50 June 2nd, 2020 at 2:46 pm
1Zer0 #48: Most physicists would probably tell you that the Bekenstein bound is derivable from GR and QM (the Second Law not being an additional assumption, but just a fact about what’s going to happen in a world at non-maximal entropy), and that it’s therefore about as solid as anything in physics. Some people, like the philosopher Tim Maudlin, strongly disagree with that. In any case, of course we’re still like 20 orders of magnitude in energy away from doing the requisite experiment, and there might be many interesting debates to be had. My point was simply that, if you want to talk about physics, then you at least need to engage with the best known physics that’s relevant to what you’re talking about (e.g., in the case of hypercomputation, quantum mechanics), rather than pretending that it doesn’t exist.
Comment #51 June 2nd, 2020 at 3:23 pm
Wyrd Smythe #34:
Oh, wait, there’s a third possible problem, one which also I alluded to in #16 above. Which is that just as it fails to imagine any sort of non-violent protest other than the most ineffectual sort, it fails to imagine any sort of violent protest other than the most undirected sort. As I said above, I find it hard to blame protesters for violence, when that violence is directed at the police who are attacking them. When it’s directed at arbitrary people and their property? That’s another matter.
In short the whole thing sets up a false dichotomy between ineffectually eschewing violence on the one hand and being undirectedly violent on the other hand. When in fact it is possible to eschew violence effectively, or to apply violence in a directed fashion.
Comment #52 June 2nd, 2020 at 3:57 pm
Sniffnoy #38
I am not clear as to your question. The Social Contract is just a political fiction at the heart of legitimising our liberal democracies. You can have other ways of trying to legitimise your political system of course. But the point is you need everyone to buy into it. If your society gets to a point where a critical threshold of people decides that the system is illegitimate then they tend to rebel against it. This leads to people who do buy into the system making value judgments that are incoherent form the perspective of people who don’t buy into the system.
Comment #53 June 2nd, 2020 at 4:01 pm
Raoul Ohio #36
The idea that voters matter is certainly a cute idea and in some instances may actually hold. However, for the US at least, the research Thomas Ferguson conclusively shows that Median Voter Theorem does not hold. Certainly not since the end of WW II.
Comment #54 June 2nd, 2020 at 4:13 pm
Allow me to be the Anti-Nick and state an opposite view so you can all see it and judge it: The reason some police behave like thugs, is that their job is to maintain order in cities that contain criminal mobs who given a chance will loot and destroy. But for some reason your culture has reality backwards, to the point that you see the mob destruction and think it’s *your* fault.
Comment #55 June 2nd, 2020 at 5:06 pm
Gerard #46,
I don’t know the answer. There are heroic cops in India one hears about too, but my sense is that that’s the exception rather than the rule. America largely feels safe and non-violent, while India largely feels dangerous and violent, atleast to me, for whatever my opinion is worth.
Here’s another implication of poor law and order : a lack of freedom of speech. I wouldn’t dare criticize local politicians in India because I wouldn’t know how to protect myself from their hired goons. Criticizing national level politicians in India is far safer. In America, I could safely do both because I trust the law and order here. In India I’d need to be from a rich or “influential” family to be this free.
Comment #56 June 2nd, 2020 at 6:11 pm
Bunsen Burner #52:
You stress the social contract as a reason for not looting, burning, etc., focusing on the government and such. But random local businesses aren’t the government. They do rely on property rights, which are government enforced, but they also rely on self-enforcement of those property rights to some extent. They have the stuff and you don’t, not just in a legal sense but also in a physical sense. They may not always have guards with guns, but I’m sure they have locks on their warehouses and they can always refuse to send more shipments or reopen.
So, the incentive to not loot and burn and such does exist even without the government or social contract, even though without such it may not dominate (being overwhelmed by the obvious free-rider problem). Because if you steal from someone — let alone if you simply destroy their things — they may refuse to trade with you in the future. That doesn’t always require a government to enforce. You attack a local business, it may not reopen. No social contract required, just thinking ahead.
Comment #57 June 2nd, 2020 at 6:19 pm
Mitchell Porter #54:
The whole question though rests in the ambiguity of that word “order”. When we say “order”, do we mean “order” as in rule of law, or “order” as in rule of man?
What the cops are on paper supposed to do, and what they should be doing in what is supposed to be a liberal democracy, is the former. But what they actually typically do, that they seem to have a culture of doing, of hiring people and training people to do, is the latter.
Police acting like thugs is indeed a way to achieve the latter sort of order; so if this were some dictatorship maybe we’d just say hey, that’s their job. But it’s not the way to achieve the sort of order we should have.
To go on a tangential rant for a moment, it really bugs me that there’s all these people calling for brutal police crackdowns saying “law and order”! Except, that’s not law and order, because that’s not law. That isn’t law and order; that’s man and order.
Similarly, the cops going around calling themselves “law enforcement officers”. Which is what they’re supposed to be. But if they were actually law enforcement officers, they’d enforce the law. When actually they go around enforcing rule of man instead. We ought to say that they are not currently law enforcement officers, but rather man enforcement officers instead. Law enforcement officers is what they are failing at being and need to become.
Comment #58 June 2nd, 2020 at 8:01 pm
This is an interesting point. You’re absolutely right that all of modern civilization is a social construct to some degree including concepts of property rights etc. But if you’re going down that path, then the idea that people should be treated equally and not oppressed is also just a social construct. Clearly this is a reasoning path that leads to nowhere.
Comment #59 June 2nd, 2020 at 8:33 pm
Bunsen Burner #53
The work you want to look at is Gilens and Page, ‘Testing Theories of American Politics: Elites, Interest Groups, and Average Citizens’
https://doi.org/10.1017/S1537592714001595
‘Multivariate analysis indicates that economic elites and organized groups representing business interests have substantial independent impacts on U.S. government policy, while average citizens and mass-based interest groups have little or no independent influence.’
Comment #60 June 2nd, 2020 at 10:12 pm
I completely praise Scott, Nick and others on acknowledging the oppressive forces underlying our society. They are not advocating looting. They are simply calling out the Trump media machine for highlighting the looting against the more prevalent backdrop of valid, legal, and justifiable civic protest.
And great podcast on Mindscape. Any time Alan Turing’s name is mentioned, its always interesting. Good job! Sean is wonderful too.
Comment #61 June 3rd, 2020 at 1:02 am
Scott #50: the Bekenstein bound holds even in confining quantum field theories so has no implications for quantum gravity.
https://arxiv.org/pdf/1906.03530.pdf
Comment #62 June 3rd, 2020 at 2:11 am
Scott#50,
Alright, thanks for elaborating. If I ever publish something about some sort of hypercomputation on any medium, I will keep in mind to mention the Bekenstein Bound.
Comment #63 June 3rd, 2020 at 3:54 am
Sniffnoy #16 “The fight you need to win isn’t physical, it’s social. And you don’t win social fights by committing violence.”
Could go either way. There’s really no guarantee that democracy works. Your vote might not be counted, or your options what to vote for might be too constrained by the media-controlled Overton window, byzantine voting rules, gerrymandering and the like. Or there might just be too many hostile voters in society.
So if you see your core priorities violated too much, you look for other leverage, the ones you would look for if you didn’t live in a democracy. The governments’ monopoly on violence is imaginary, as is the so-called social contract. And I think that’s a good thing, because if they had an actual monopoly on violence, you’d be their slave and you sure as hell wouldn’t get to vote.
I see it as an ultimatum game in game theory. ‘Nice economy you’ve got there, would be a real shame if something happened to it.’ Murder-suicide follows a similar logic.
Comment #64 June 3rd, 2020 at 5:13 am
Brandon #58
Of course the idea that people should be treated equally and not oppressed is just a social construct, how could it be otherwise, unless you believe in supernatural entities. Far from leading nowhere it has allowed us to greatly expand our concept of ethics and social structure.
Comment #65 June 3rd, 2020 at 5:19 am
Sniffjoy #56
I still don’t know the point you are making. Without the government there would be no business, local or otherwise. There would be no locks or guns either. You would just have naked guys living caves trading rocks and sticks. Social organisation is needed to have a functioning society, and hence will also require a system of governance. This must be grounded in some sort of conceptual scheme that the populace find acceptable. Look, for more of this just go read some undergraduate texts in political philosophy.
Comment #66 June 3rd, 2020 at 5:22 am
ira #59
Thanks for the link. I was originally thinking of Ferguson’s 1995 work as given in the citations. I guess it’s interesting that people are still doing research in this, a bit depressing though that they are still getting the same answer 🙁
Comment #67 June 3rd, 2020 at 6:23 am
” As someone who was once himself the victim of a crazy police overreaction (albeit, trivial compared to what African-Americans regularly deal with),”. ONCE? where in this country have you lived?. i have been subjected to mistreatment by various authorities my entire life, specifically because of my identified as a jew (and my father had to change his name from Goldstein to Gaylord in order to get hired by DuPont which, like many companies did not knowingly hire jews. the two chief advantages i have had bei]ng a jew in America rather than a black in America is that (1) my religion could be ‘hidden’ by a name change, and (2) the culture i was raised and educated in emphasized eduction above all else (eg., i went to high school in the hometown of Bell Laboratory in Murray Hill, NJ). IT’s undoubtably difficult to be black in America but don’t delude yourself about the anti-semitism that is also an integral part of the American experience.
Comment #68 June 3rd, 2020 at 9:42 am
Jghyy #61: Sorry! As I’ve done in the past, I conflated the Bekenstein bound (which was originally derived from black hole considerations but which turns out also to hold in non-gravitational QFTs) with the holographic bound (which really does involve gravity and which Bekenstein was also involved with).
But also, the Bekenstein bound clearly does have implications for QG (indeed, it’s used to derive the holographic bound)! So I think you meant the converse: QG has no implications for the Bekenstein bound.
Comment #69 June 3rd, 2020 at 9:48 am
1Zer0 #62: If you’re writing a paper, and there’s some consideration that completely destroys or changes the paper’s thesis, a lot of people seem to have the idea that it’s good enough to mention the consideration, in some note near the end, so no one can accuse you of not knowing about it. The right way, instead, is to take the consideration fully on board from the beginning.
Comment #70 June 3rd, 2020 at 10:47 am
Bunsen Burner #65
> Without the government there would be no business, local or otherwise.
There are a lot of people that would dispute that point and I think they have a fair amount of evidence on their side.
There are and have been societies with practically no functioning government, yet life and business goes on. Some examples would be many less developed countries today, and parts of the American west during the late 19th century. Though I’m not an expert I suspect the early Roman Republic also lacked many of the functions that are deemed essential for modern governments, such as a police force.
Comment #71 June 3rd, 2020 at 11:35 am
Scott, while listening to the podcast, I started wondering why fully-deterministic quantum polynomial time isn’t that well studied; we usually compare P vs BQP. Why don’t we compare BQP and BPP or vs P? Do we know whether it is _equal_ to P and thus a little bit boring?
Comment #72 June 3rd, 2020 at 11:48 am
Richard Gaylord #67: I guess I’m lucky to have experienced obvious antisemitism only over the Internet, never face-to-face. But also, some people guess that I’m Jewish from looking at me but most don’t. In any case, I agree that African-Americans have had a harder run of things than Jews have in the US!
Comment #73 June 3rd, 2020 at 12:13 pm
Gerard #70
My comment was about modern large scale high tech societies. I am not aware of any countries today that do not have a functioning government that are also not failed states where life and business only goes on in a very restricted sense.
Comment #74 June 3rd, 2020 at 12:42 pm
Gerard #70
The question about the necessity of government is an interesting theoretical one, but just let me say this for now:
Unless you were wealthy and/or had sufficient weaponry you would NOT want to live in a ‘less developed’ country that had no government.
Comment #75 June 3rd, 2020 at 1:45 pm
Scott, you mentioned that mathematicians can feel P!=NP as a sort of invisible fence appearing in many seemingly unrelated places. One way to understand that is: you try to prove X, you can’t, after some time you realize it’s actually as difficult as proving P=NP (then you can safely bet X can’t hold). One other way to understand that is: you try to prove X, you can’t, and after some time you realize it’s actually as difficult as *either proving or disproving* P=NP (then you can safely bet you’re screwed). Which one is closer to what you had in mind (if any)?
This is the kind of feeling I can imagine for someone trying to construct a free energy machine, then facing again and again many seemingly unrelated technical issues, but of course the problem is thermodynamics so whatever how brillant you are at solving technical issues, it’s safe to bet you’ll always find another seemingly technical problem. My question for you: why do you think it’s so hard to *either prove or disprove* P=NP? Why does this need to be an invisible fence rather than a straightforward diagonal proof of some sort? What would go wrong if it was too easy to prove P!=NP? (yes, that’s the same question 🙂 )
(I’ve read someone arguing that it’s because P!=NP, but that doesn’t seems to make sense as proving this separation is a finite instance, not a complexity problem by itself)
(as for the societal issues… I was impressed to see many police officers kneeling in front of the manifestants, a bit like the tank man at Tiananmen desperately trying to both obey orders and not kill anyone in the process. Thank you, bros.)
Comment #76 June 3rd, 2020 at 2:04 pm
student of the book #75: I’d say that proving P≠NP is less like scaling an invisible fence than like climbing an incredibly tall mountain. Proving impossibility is almost always inherently harder than discovering something to exist, but computer scientists have managed to prove weaker separations, including for example NEXP⊄ACC a decade ago. Anyway, read my paper for much, much more about this, including what I see as the asymmetries between proving P=NP and proving P≠NP!
Comment #77 June 3rd, 2020 at 3:55 pm
Bunsen Burner #65:
Yes, I’m aware of these ideas about the “state of nature”. I think what we actually know about history at this point shows them to be wrong. I’d suggest reading David Friedman’s “Legal Systems Very Different From Ours” (link goes to a free online draft) for some examples of how actual societies with far less of what we think of as government have looked. (Note that the book covers other things too, but I can try to pick out the most relevant chapters if you like.)
Even if you want to make the claim that things would necessarily be primitive without government, that would not be “naked guys living caves trading rocks and sticks”. Primitive peoples were/are much more advanced than you seem to be giving them credit for, and the same basic mechanisms and incentives would indeed apply in that state. Consider that states as we know them barely existed until around the dawn of history or so, but there was a lot of technological development prior to that during the neolithic. The old idea of the “state of nature” is, quite simply, not an accurate reflection of how things actually occurred.
Comment #78 June 3rd, 2020 at 3:59 pm
Andaro #63:
Even if I spot you most of that, the question then remains, wouldn’t it be better to exclusively attack police, government buildings, etc., rather than third parties?
Comment #79 June 3rd, 2020 at 4:38 pm
Scott #2:
Btw, I think a better word for the sort of training you describe might be “paramilitary” maybe? I saw this word used somewhere to describe and I was like, oh hey that does seem to be an appropriate description…
Comment #80 June 3rd, 2020 at 5:31 pm
Bunsen Burner,
Of course Median Voter Theorem doesn’t hold with any accuracy. What does that have to do with anything? Does that mean voting doesn’t matter?
Comment #81 June 3rd, 2020 at 5:47 pm
Gerald #70,
you can check how your theory holds in the “old american west”. A lot is recorded. By a coincidence, trans continental and Atlantic telegraphs were becoming mainstream, and US East Coast and European newspapers had a big hit covering US West gun fights. That’s why the “OK Corral” is known everywhere.
Before police, towns would hire gunfighters to shoot it out with the outlaws. The gunfighters themselves were often former outlaws who saw that a paycheck was better money than robbing saloons. It is a likely guess that a lot of accidents happened.
Some of the gunfighters parlayed the news coverage into better careers: Bat Masterson bacaue a NYC sports writer. Wyatt Earp’s pall bearers (1929) were mostly movie stars who had played him in movies.
Comment #82 June 3rd, 2020 at 5:49 pm
Loved the interview, fascinating stuff! I’m just learning about complexity and TCS more broadly as a hobby, so forgive me if I ask a dumb question. Am I correct that recursive Fourier sampling is not known to be in the polynomial hierarchy? If so, Has there been any progress in showing this?
Comment #83 June 3rd, 2020 at 6:37 pm
Mike #82: Recursive Fourier Sampling is conjectured not to be in the polynomial hierarchy (as an oracle problem), but it’s been open to show that for 27 years. The obvious progress is that two years ago, Raz and Tal showed that a different BQP oracle problem (Forrelation) is not in PH, which removed a lot of the motivation to show the same thing for Recursive Fourier Sampling (although perhaps not all of it). You could also look at some work by Zach Remscrim some years ago, on the polynomial degree of RFS.
Comment #84 June 4th, 2020 at 12:49 am
You know, I’ve never thought about randomness in the context of PSPACE.
With unbounded time, i guess probabilities become mostly irrelevant? They might as well be booleans at that point (zero or non-zero).
On the other hand, doesn’t unbounded time also enable arbitrary precision for probabilities?
What’s stopping us from using a random bit as storage?
In PSPACE, you can certainly read an arbitrarily long string corresponding to the probability of a given outcome, if it’s long enough.
But what about writing a string as a probability? How much information can you pack into a probability using at most polynomial space?
And isn’t it different depending on whether you’re using quantum vs classical bits? Is quantum PSPACE != PSPACE? 🙂
Comment #85 June 4th, 2020 at 2:08 am
Scott #5
I think audience of podcast vs this blog matters in this context. I am like those people who gather near Kennedy space center and gawk at launch (and now landing) of rockets. I can understand the enormity of the visuals but have absolutely no capability to fully understand what is involved in making it happen or make a small contribution. So the expert, has to necessarily moderate or apply a low pass filter to all the thoughts about a subject, lest they turn off the audience. You don’t have to apologize for necessarily dumbing things down for people like me.
By the way, I never smiled/laughed while reading a technical book. I am now at “paleo complexity” chapter in QCSD and I have already had more fun reading it than any of the previous 10 fiction books.
Also similar to Ryan, when are you recording your classes and posting them online. It would be great to learn from you in a course context.
Comment #86 June 4th, 2020 at 2:29 am
Deepa #55
Comparing one society to a far worse one (or even a slightly worse one) and saying oh ok we are doing better will only lead to stagnation. Society will not improve, will not continuously reduce inequality or inequity. While it is fine to occasionally feel happy about how one’s society is better in relation to other, road to utopia is paved with continuous struggle for improvement.
Comment #87 June 4th, 2020 at 2:36 am
Job #84: PSPACE = BPPSPACE = BQPSPACE = PPSPACE. These equalities are not completely obvious but were shown a while ago; see for example here.
Comment #88 June 4th, 2020 at 2:42 am
Eric #71:
while listening to the podcast, I started wondering why fully-deterministic quantum polynomial time isn’t that well studied; we usually compare P vs BQP. Why don’t we compare BQP and BPP or vs P? Do we know whether it is _equal_ to P and thus a little bit boring?
Good question! The class you’re talking about is “EQP” (Exact Quantum Polynomial-Time), which Bernstein and Vazirani discussed along with BQP back in 1993. No, EQP is not known to equal P, and there’s been a fair amount of interesting research on exact quantum algorithms and query complexity. But EQP is generally considered “unphysical”—since not only can a real quantum computation never be implemented perfectly (if nothing else, there will always be small errors in the angles of the unitary rotations), but crucially, the very definition of EQP probably depends on the choice of gate set. I.e., unlike with BQP, we don’t seem to get a single, well-defined complexity class that’s independent of low-level hardware choices.
Comment #89 June 7th, 2020 at 2:06 pm
Sniffnoy #78: Yeah, makes sense. But it depends on how good you are at directly killing the police. If you’re really bad at it, damaging the economy that feeds them is a decent second best option. If you live in a country with a strong welfare system, you can even use legal means to do so without violence. I personally feel completely alienated from politics, the media, and society, but for some inexplicable reason they send me money every month even though I’ve ended my career deliberately. I consider it tribute that buys my nonviolence.
I don’t like people, but I do like their goods and services. 🙂
Thanks for the interaction, I retire from the internet now. I’m really really tired of communicating with human beings.