The Complexity Zoo needs a new home
Update (Nov. 14): I now have a deluge of serious hosting offers—thank you so much, everyone! No need for more.
Since I’m now feeling better that the first authoritarian coup attempt in US history will probably sort itself out OK, here’s a real problem:
Nearly a score years ago, I created the Complexity Zoo, a procrastination project turned encyclopedia of complexity classes. Nearly half a score years ago, the Zoo moved to my former employer, the Institute for Quantum Computing in Waterloo, Canada, which graciously hosted it ever since. Alas, IQC has decided that it can no longer do so. The reason is new regulations in Ontario about the accessibility of websites, which the Zoo might be out of compliance with. My students and I were willing to look into what was needed—like, does the polynomial hierarchy need ramps between its levels or something? The best would be if we heard from actual blind or other disabled complexity enthusiasts about how we could improve their experience, rather than trying to parse bureaucratese from the Ontario government. But IQC informed us that in any case, they can’t deal with the potential liability and their decision is final. I thank them for hosting the Zoo for eight years.
Now I’m looking for a volunteer for a new host. The Zoo runs on the MediaWiki platform, which doesn’t work with my own hosting provider (Bluehost) but is apparently easy to set up if you, unlike me, are the kind of person who can do such things. The IQC folks kindly offered to help with the transfer; I and my students can help as well. It’s a small site with modest traffic. The main things I need are just assurances that you can host the site for a long time (“forever” or thereabouts), and that you or someone else in your organization will be reachable if the site goes down or if there are other problems. I own the complexityzoo.com domain and can redirect from there.
In return, you’ll get the immense prestige of hosting such a storied resource for theoretical computer science … plus free publicity for your cause or organization on Shtetl-Optimized, and the eternal gratitude of thousands of my readers.
Of course, if you’re into complexity theory, and you want to update or improve the Zoo while you’re at it, then so much the awesomer! It could use some updates, badly. But you don’t even need to know P from NP.
If you’re interested, leave a comment or shoot me an email. Thanks!!
Unrelated Announcement: I’ll once again be doing an Ask-Me-Anything session at the Q2B (“Quantum to Business”) conference, December 8-10. Other speakers include Umesh Vazirani, John Preskill, Jennifer Ouellette, Eric Schmidt, and many others. Since the conference will of course be virtual this year, registration is a lot cheaper than in previous years. Check it out! (Full disclosure: Q2B is organized by QC Ware, Inc., for which I’m a scientific advisor.)
Follow
Comment #1 November 12th, 2020 at 1:20 pm
I can’t even… How is it possible for a mathematics wiki to be banned by university bureaucrats due to incompliance with accessibility regulations?! Whoever is responsible for that regulation belongs in a real zoo, not a complexity one.
Comment #2 November 12th, 2020 at 1:23 pm
Given that several US universities have recently entered into a settlement [1] that requires all publicly available content to be accessible, I think you’ll find many otherwise eager hosts cannot help you. Have you considered hosting it at UTA?
[1] https://accessibility.mit.edu/captioning/mit-nad-agreement
Comment #3 November 12th, 2020 at 1:26 pm
myst_05 #1: I don’t blame IQC—they were gracious enough to host the site for 8 years, and are just trying to follow rules from above. If my experience is any guide, the issue likely involves bureaucrats at a higher level who suffer from an impairment far more serious than blindness, deafness, or anything else that’s merely physical.
Comment #4 November 12th, 2020 at 1:31 pm
I’m not prepared to host the Zoo, but I did manage to get MediaWiki installed for my own site even though I’m on Bluehost. I don’t remember it requiring any technical skill. So you might want to reinvestigate doing that.
Comment #5 November 12th, 2020 at 1:35 pm
David Karger #2: Do you find it ironic that a central effect of these accessibility policies seems to be to make free academic content less accessible than before?
The Complexity Zoo is not exactly a well-heeled outfit with fully-staffed legal and compliance offices. 🙂 If an actual human wrote to me and said, “here’s how you can make the Zoo more accessible to blind people,” or whatever, and it wasn’t inordinately hard, of course I’d do it (or get a student to do it). But my own accessibility problem is that I can’t speak bureaucratese, only English and very poor Hebrew.
Comment #6 November 12th, 2020 at 1:58 pm
Pragmatically, as it’s a small sizes site with medium traffic, what would prevent you from self hosting the site on the MS Azure Cloud for example? It’s usually reasonably cheap even for small sized sites + you can probably easily fundraise the cost here. Server administration and especially security can be reasonably well automated on Azure.
Comment #7 November 12th, 2020 at 2:23 pm
1Zer0 #6: That could work (someone else suggested it by email), except I have no idea how to set up MediaWiki — on Azure, Bluehost, or anywhere else.
Maybe I should have added: I can easily pay hosting costs from my research funds, if needed. The limiting factor is not money; it’s just someone who’s web-savvy enough to make these things happen (and who’s then reachable later if the site goes down).
Comment #8 November 12th, 2020 at 2:30 pm
I could help set up hosting on AWS. If the traffic is fairly small it may qualify for their “free-tier”. Even if it doesn’t, it should be very affordable.
Comment #9 November 12th, 2020 at 2:31 pm
I have no experience hosting MediaWiki stuff but if you could send me a zip or whatever of the zoo (to the email listed in the comment), I would be happy to take a crack at it.
Comment #10 November 12th, 2020 at 2:37 pm
As a long time reader and fan, I just feel embarrassed the first time you discuss accessibility is when forced to face some inconvenience. True, accessibility should be granted whatever tools you use for your website, rather than some afterthought one need to take care the hard way. Hopefully this new wave of regulation will help fix that. Enlightenment, right?
Comment #11 November 12th, 2020 at 2:43 pm
Unfortunately, I do not have the bandwidth for managing a site with PHP and MySQL. I do however want to use this example as a cautionary tale for readers of this blog: for sites like this (information dense, but needs to be changed infrequently by a small team of pople) using a static site generator is much much better and easier to manage.
Comment #12 November 12th, 2020 at 3:14 pm
Dear Scott,
Maybe Neil Sloane would be able to help out, or refer you to some folks who could, as the OEIS Wiki uses a MediaWiki platform they did considerable upgrading on to render it suitable for math applications.
Regards,
Jon
Comment #13 November 12th, 2020 at 3:16 pm
The LessWrong team may be interested in hosting this; we’ll send you an email. (We consider our scope to be intellectual-infrastructure-in-general, not just LessWrong.)
Since this is a site running MediaWiki, accessibility is mostly the responsibility of the MediaWiki developers, not you (as a user). Looking over it briefly, it looks like the main accessibility issues are already well handled; I don’t see any obvious problems. (I’m assessing this as a sighted web developer looking at technical aspects; I don’t use a screen reader myself.)
The main trouble spot is going to be screen-readers tripping over mathematical notation. MediaWiki is already doing the right thing for you: LaTeX math is rendered as images, with alt-text which is the LaTeX source code. There are also some bits of non-LaTeX math notation, using unicode characters and subscript/superscript tags; I wouldn’t be surprised if some screenreaders tripped over that, but those cases are really the responsibility of the screen-reading software authors, not the authors of individual web sites.
(But of course, if the issue is whether you can convince a risk-averse bureaucrat with no ability to assess accessibility themself, then actual accessibility might not matter.)
Comment #14 November 12th, 2020 at 3:26 pm
friend of the visually impaired #10: I’d be thrilled to make the Complexity Zoo more accessible to visually impaired people. I genuinely don’t know what’s needed for that. Like, what goes wrong if you just use existing HTML readers—is the issue the subscripts and superscripts? If so, how do you fix it? I’d love to hear from anyone who knows about HTML accessibility, and is also at least passingly familiar with the Zoo.
(I’m friends with at least one brilliant complexity theorist who happens to be blind: Steven Rudich. Maybe I should ask his advice?)
The point you need to understand is that this new Ontario regulation gave me no guidance whatsoever about how to solve the problem—zero. It simply said: “Either do something that you have not the slightest idea how to do, or else you need to take down your entire free resource, thereby making it completely inaccessible to everyone, visually impaired or not!” In other words, the contribution to “accessibility” was purely a negative one.
It reminds me of California’s infamous SB5 law, which “solves” the problem of independent contractors not having enough job security, by essentially decreeing that no one is allowed to be an independent contractor anymore—thereby destroying thousands of livelihoods. (Last week, California voters approved a narrow exemption to SB5 for Uber and Lyft drivers. A better solution might’ve been complete repeal of SB5, remedial economics classes for everyone involved in it, and a universal basic income.)
I fear that these are the kind of “solutions” that result when you take genuine problems and then pass them through minds that are unequal to those problems, or possibly any problems.
Comment #15 November 12th, 2020 at 3:59 pm
Isn’t mediawiki the same software that powers Wikipedia itself ? Does that mean that Wikipedia isn’t accessibility standards compliant ?
Comment #16 November 12th, 2020 at 4:24 pm
Moshe Zadka #11:
for sites like this (information dense, but needs to be changed infrequently by a small team of pople) using a static site generator is much much better and easier to manage.
I generally agree! But people kept emailing me little additions and changes, and I no longer had time to implement them all by hand. So when someone offered 15 years ago to make the Zoo into a wiki, I readily agreed! And now, without a big painful conversion, there’s no going back…
Comment #17 November 12th, 2020 at 4:26 pm
James Babcock #13: Thanks so much! I got back in touch with the LessWrong team. Let’s give that a go and see if it works.
Comment #18 November 12th, 2020 at 4:49 pm
A few questions, for you or others:
There are probably also some questions around MySQL, which I think is what it would be using as its database.
Comment #19 November 12th, 2020 at 5:18 pm
Since you used to be a student at Berkeley, it might also be worth trying the Berkeley Open Computing Facility, which offers free life-time web hosting (see https://www.ocf.berkeley.edu/docs/services/web/)
Comment #20 November 12th, 2020 at 6:35 pm
I’m a Wikipedia editor and have considered copying the Complexity Zoo and uploading it to Wikipedia for a while. No one will need to host it if we have Wikipedia doing it for us. I would appreciate feedback on this idea before I follow through.
Comment #21 November 12th, 2020 at 6:46 pm
FWIW, I propose GitHub Pages as a host for the Complexity Zoo. It’s (essentially) free and comes with any GitHub account, so as a moderately tech-savvy GitHub user, I might be able to set this up. (Unfortunately, I don’t know about working with MediaWiki, so I guess I’ll have to learn everything I need to on the fly.)
Alternatively, GitHub also natively supports wiki creation for any code repo, so the Complexity Zoo could go there as well. However I feel iffy about using the wiki for something very different than the intended usage, which is code documentation.
(I hereby swear that none of this comment was paid for or is an endorsement; I just happen to find this to be useful.)
Comment #22 November 12th, 2020 at 7:24 pm
Victory Omole #20: That’s a very interesting proposal! I’m totally happy for you to do that. Having said that, I’m curious about how exactly it would work. Would the content of the Zoo simply be integrated into the usual Wikipedia (creating articles for complexity classes, and adding material to existing articles)? Over the years, that’s already happened to a great extent, thus reducing the need for the Zoo, although I think there’s still lots of stuff in the Zoo that’s not in Wikipedia. Or would the Zoo become its own separate walled-off section of Wikipedia? Particularly in the latter case, wouldn’t other editors need to approve your plan? And what if they flagged some complexity classes for deletion for not being notable enough? 🙂 Thanks!!
Comment #23 November 12th, 2020 at 7:59 pm
Scott #22:
> Would the content of the Zoo simply be integrated into the usual Wikipedia (creating articles for complexity classes, and adding material to existing articles)?
Yes, all articles will be tagged with the “Complexity classes” category. Most of the Complexity Zoo’s homepage can be moved to the List of complexity classes Wikipedia page.
> And what if they flagged some complexity classes for deletion for not being notable enough?
This will not happen since all the Complexity classes in the zoo have sources (I hope!).
Comment #24 November 12th, 2020 at 8:08 pm
@Scott #5: “Do you find it ironic that a central effect of these accessibility policies seems to be to make free academic content less accessible than before?”
I don’t think there’s anything ironic about it. I think that is the real intent of the policies. In the year 2020, it astonishes me how many people still haven’t figured out that our civilization is based mostly on information warfare, and the little guy’s voice must be squeezed out at all costs.
Never ascribe to incompetence that which is adequately explained by malice. (For some reason, this maxim is frequently delivered backwards. Part of the information war, I guess.)
I’m generally a placid, happy guy, but one of the few things that makes me truly angry is the fact that the ADA prevents me from making my lectures available to the public. This part of the ADA should be overturned; it does a thousand times more harm than good. I do not believe in the good intentions of those prosecuting these policies. Satan is real, and this is part of his plan.
Comment #25 November 12th, 2020 at 8:58 pm
Scott
There’s a question I’ve been wanting to ask you once you posted something more CS related. Hopefully this is close enough.
If it were proved that $$NP = P^{\#P}$$, therefore implying that $$NP = BQP$$
how would that affect your beliefs about P vs NP ? Assume you have no information about how the proof works, only that it exists. In other words the only additional piece of information you have for updating your beliefs is the bare fact I hypothesized here.
Comment #26 November 12th, 2020 at 9:02 pm
Victory Omole #23: In that case, may the oracles smile upon your effort! Thanks for doing this!
Comment #27 November 12th, 2020 at 9:15 pm
Professor #24: I’m pretty cynical, but I confess my imagination falters when I try to picture the accessibilitycrats in their arugula-filled basement room, cackling to each other about crushing the little guy and his Complexity Zoo. I think they genuinely wanted to help but, as often happens, devised a policy that ended up either being wildly counterproductive, or at least having major unintended consequences.
Comment #28 November 12th, 2020 at 9:25 pm
Gerard #25: NP=P#P is not known to imply NP=BQP. It does imply BQP⊆NP, but as far as we know it’s consistent with P=BQP≠NP, or P≠BQP=NP, or P≠BQP≠NP, or P=BQP=NP (one can probably construct relativized worlds where all four possibilities hold, although I haven’t verified that).
To answer your question, though, if NP=P#P I’d be shocked—we would’ve been just massively wrong about complexity classes—and that would have to raise my probability for an even more dramatic collapse like P=BQP=NP=P#P.
Though note that there’s an irony here: if NP=P#P, then some new separations would also follow from that statement, such as P#P≠NEXP and NEXP⊄P/poly !
Comment #29 November 12th, 2020 at 9:48 pm
Can’t recommend getting tangled up in Wikipedia cultism. Just for starters the “No Original Research” rule is a constant obstacle to building any sort of learning community, but if you go that route you might try Wikiversity instead. It’s generally speaking a more friendly environment and it’s easier to create group projects there without a lot of hassle.
Comment #30 November 12th, 2020 at 9:56 pm
Scott #27: I think the winner of the cynicism contest should actually be the one who believes the parties responsible have good intentions, since it’s part of a cynical worldview in which the hard work of good people causes harm. Cynicism is something like not believing in causes, so if you can’t even believe in the causes of good people, that’s champion cynicism.
Comment #31 November 12th, 2020 at 10:27 pm
I am a big fan of and contributor to Wikipedia but I don’t think Wikipedia itself is a good home for this. The main reasons are that
– Wikipedia requires every topic to be independently notable (meaning, for technical topics like this, covered in depth by multiple independent publications) and I think that’s likely to be untrue for some of the more minor complexity classes.
– Wikipedia requires every claim in its articles to be backed by published sources, making it difficult to say some of the things we would want to say about complexity classes that might be obvious and not require citation to a complexity theorist (and therefore have not yet been explicitly written out in any publication) but are beyond the average Wikipedia editor.
– The Complexity Zoo is itself mentioned in nearly 70 Wikipedia articles, in many cases as a source. If it were part of Wikipedia it could not be used as a source for other Wikipedia articles and any claims based on its content would need to be removed or re-sourced.
Wikibooks might be a possibility though.
Comment #32 November 12th, 2020 at 10:31 pm
Sounds like there are some promising possibilities already! In any case, Beeminder would be honored to host it. We launched in 2011 so, by Lindy’s Law, you can expect us to be around for… approximately ever and ever. Longer than IQC hosted it in any case!
(So ironic about IQC not being able to make it accessible on their servers anymore due to it being insufficiently accessible! It reminds me of the concept of price gouging. Charging an offensively high price means only the desperate can afford it, so… better instead effectively charge infinity dollars so _no one_ can afford it? Facepalm! I guess that’s a philosophical can of worms, and, like you say, IQC was kind to host it as long as they did! Point being, I, on behalf of Beeminder, can commit to hosting it indefinitely on our servers if you deem us the best option. We probably don’t make as much sense as LessWrong or Wikipedia itself (!), but, well, you have options, is the point!)
Comment #33 November 12th, 2020 at 10:31 pm
Without actually seeing the regulations, it’s hard to know what’s going on. But I have had the experience of working on the website of a university lab, only to have it remade completely when the bureaucracy mandated that all university websites be made using a specific “content management system” (CMS). This is a way for the university-level administration to easily ensure uniformity, e.g. so that all the university’s websites conform to whatever marketing, legal department, etc currently prefer (logos in the right place, legal disclaimers everywhere).
So I am led to wonder whether the University of Waterloo has similarly decided to meet the Ontario regulations by working within a particular CMS, and so using MediaWiki just doesn’t fit the plan.
Comment #34 November 12th, 2020 at 11:06 pm
I can help you run this.
I’ve set up MediaWiki before. This was some years ago, but I think I still remember how. 😉
I currently work as a sysadmin for a small startup. I have an amateur interest in complexity theory, but no formal education in it. I’m an undergraduate CS student.
Based on the page hits on your site statistics (https://complexityzoo.uwaterloo.ca/Special:Statistics), assuming those hits were gotten over 3 years (a pessimistic assumption) that’s about 3 hits/minute. You could host this on a fairly low-end VM, running about $5-20 per month. That’s small enough that I could probably convince my employer to sponsor the project. (Of course, it sounds like money isn’t the real constraint, but spare time.)
Send me an email if you’re interested.
Comment #35 November 13th, 2020 at 2:26 am
Scott, I really enjoy your humor and metaphors about the zoo idea,
really interested, and wanna be a forever assistant to your blog (until my death of coz~)
Given that I have no experience about how to run a blog while others may have over 10 years of experiences…
Maybe you could still consider me as one of them on your waiting list. not keep it updating or in order.
But add more exciting, unpredictable, magical elements: randomness and chaos.
Since I am good at making trouble ,lazy, procrastinating,forgettable, lame-English user…
Oh! That’s how Alexander Fleming accidentally discovered Penicillin(but no promise, still you got all copyright as you’ve said, but add risks as well)
Consider me please~^^
Comment #36 November 13th, 2020 at 3:14 am
I’d love to help improve The Zoo.
Comment #37 November 13th, 2020 at 3:37 am
I don’t see any note about the license of the content of the wiki anywhere. That’s a pity, because if it were under a free license (like Creative-Commons BY-SA), it would be possible to host it on Wikimedia (the organization behind Wikipedia) servers as an unofficial community project. (But I know, that using such a license may seem scary)
Comment #38 November 13th, 2020 at 3:55 am
Victory Omole #23: Another Wikipedia editor here. Sorry, I don’t believe moving things to Wikipedia will work. Most classes there are only of relevance to experts. In fact, some classes are only discussed in a single article that defined them, so they definitely won’t meet Wikipedia’s notability criteria. Also the language would have to be adapted to be much less technical and accessible to the general public – a pointless endeavour for many of the more technical content. Since most classes have extremely short descriptions, they also would immediately look really bad as articles on Wikipedia – it’s just a very different kind of content. Finally, someone would have to take the responsibility for maintaining the flood of anonymous spam edits to these pages (“let me add a link to my proof that P=NP”) – a lot of unnecessary effort.
Comment #39 November 13th, 2020 at 6:07 am
Victor Omole #20 and Scott following: putting it on wikimedia infrastructure is probably counterproductive because of their content policies about sourcing etc. The result will surely be typical wikipedia edit wars and good content getting reverted. Some years back they ran a very famous CS theorist off the site over something like that (I better not post names in public here but can email Scott if he wants details). The thing to remember is that “Randy from Boise”, a close relative of Roofus McLoofus, is basically in charge. For something like the Zoo it’s sufficient imho to have a few regular maintainers who actually know the subject area and have authority to make editorial decisions about whether Randy/Roofus’s contributions are up to snuff.
The actual hosting expenses for something like the zoo should be close to zero, so it’s mostly a matter of having some kind of institutional home that will be around for a while. My school had a CS grad students’ association and maybe MIT or UT has something similar. That might be the best type of organization.
Comment #40 November 13th, 2020 at 6:12 am
Everyone: Thanks so much for all the generous offers to host! I decided to ask the hosts of LessWrong, since I liked the facts that (1) there’s an organization known to me with some continuity, and (2) they’ve successfully run stable websites for more than a decade. But if that doesn’t work out, I’ll move on to another of the kind offers here!
Comment #41 November 13th, 2020 at 6:22 am
Victory Omole #23 and Marcin Wrochna #38: To clarify, when I said Victory was totally welcome to appropriate Zoo content for Wikipedia, I meant
(1) in addition to, not instead of finding another new host for the Zoo,
(2) consistently (of course) with whatever Wikipedia’s policies are, and
(3) presumably along the lines of the appropriation that’s already taken place.
I completely agree with all the points made about why it wouldn’t work to take Zoo entries and make them into Wikipedia entries as is. The style is totally different, many classes might not satisfy the notability requirement, and many statements about the classes might be “original research.”
Comment #42 November 13th, 2020 at 6:30 am
Elazar #36: That’s great! Because the Zoo is a wiki, you can start making improvements right away; you don’t even need to ask permission.
I’d suggest:
– Going through the Zoo entries and seeing if you notice anything that’s missing or wrong
– Going through the last 10 years’ proceedings of the major CS theory conferences (STOC, FOCS, CCC, ITCS, QIP…), as well as ECCC and cs.CC on arXiv, and seeing if there are new classes to add, or new results about existing classes
Comment #43 November 13th, 2020 at 8:27 am
Mitchell Porter #33:
Here is a link to the Ontario regulations, which mandate that public websites adhere to the WCAG 2.0 Level AA. The link to the regulations can be found here:
https://www.ontario.ca/page/how-make-websites-accessible
The WCAG 2.0 guidelines can be found in the following link below:
https://www.w3.org/TR/UNDERSTANDING-WCAG20/Overview.html
Comment #44 November 13th, 2020 at 8:46 am
hi scott,
for accessibility improvements, I’d guess the easiest thing you could do would be to update your MediaWiki instance. It looks like Complexity Zoo is running 1.20 while the latest release is 1.35.
Just scanning through Complexity Zoo’s HTML vs an up-to-date instance, it looks like a later version of MediaWiki would have more ARIA attributes, suggesting the developers have put more work into accessibility since 2013.
Comment #45 November 13th, 2020 at 9:24 am
Comment #41:
Thanks for the feedback everyone! After reading your comments, i agree that the zoo should be hosted elsewhere. I still plan to improve the shape of the complexity classes in Wikipedia using the zoo as a reference.
Comment #46 November 13th, 2020 at 10:46 am
Scott #28
> \(NP=P^{\#P}\) is not known to imply NP=BQP.
Ah, sorry, I forgot about that diamond diagram.
> if \(NP=P^{\#P}\) I’d be shocked—we would’ve been just massively wrong about complexity classes
Why is that ? Have people really put that much effort into trying to find an efficient counting algorithm given an NP oracle (at least compared to the amount of effort that has gone into finding efficient algorithms for NP-complete problems) ? I would think not since it wouldn’t have any practical applications (unless you happen to have such an oracle lying around).
Comment #47 November 13th, 2020 at 12:18 pm
I’m not sure why you think the election is over or that Trump is likely to peacefully leave, but I’ll just leave the following link, where you can see the current mood and opinions of Trump supporters.
https://thedonald.win/
There’s a some misinformation there, but some bits of truth. You’ll probably find it interesting. If you really want to understand them, take a look.
Comment #48 November 13th, 2020 at 12:24 pm
Gerard #46: If NP=P#P, then the entire polynomial hierarchy would collapse to NP=coNP. Pretty much only P=NP itself would be a more dramatic refutation of what complexity theorists had thought the universe was like.
Comment #49 November 13th, 2020 at 12:34 pm
Scott #48
> Pretty much only P=NP itself would be a more dramatic refutation of what complexity theorists had thought the universe was like.
OK, but what actual evidence do they have that the universe is the way they think it is ?
Comment #50 November 13th, 2020 at 1:47 pm
Gerard #49: I mean, would you say that there’s “evidence” for P≠NP? Like, 60+ years of people looking for efficient algorithms for all of NP and failing, or what I’ve called the “invisible electric fence” separating the problems in P from the NP-complete problems? If so, then presumably that same evidence is also evidence for NP≠coNP. After all, people have also been looking for short certificates of unsatisfiability and failing, and a single NP-complete problem that was also coNP-complete would yield NP=coNP, but out of thousands of known NP-complete problems not a single such example has ever been found. And recall, NP≠coNP is already enough to imply NP≠P#P.
Comment #51 November 13th, 2020 at 3:40 pm
It looks like the complexity zoo has been in maintenance mode for a while now.
I can understand Waterloo’s IQC wanting to reduce the number of sites that they’re responsible for.
More than the hosting costs, it’s the whole process of keeping things up to date.
Dependencies break, vulnerabilities are discovered, patches are required.
And then there’s stuff like accessbility standards, or regulations like GDPR.
What’s strange to me is that people have not been contributing to the zoo.
Where are computer scientists cataloguing all of the different classes and relationships?
Are these being defined implicitly in sites like MathOverflow, in the form of questions and answers?
Also, looking at the various platforms out there, i’m not sure any is really a good fit for the complexity zoo.
I would want something like a wiki but with a more formal data model (like a truth graph) that we just add nodes and edges to.
Comment #52 November 13th, 2020 at 3:53 pm
Dreamhost is one hosting provider that lets its users set up Mediawiki instances; that’s where I host my personal sites, so I could set it up there if nobody else is able to. (I’m not sure about how to transfer existing content from another Mediawiki instance there, though.)
Comment #53 November 13th, 2020 at 4:07 pm
Scott #50
> would you say that there’s “evidence” for P≠NP? Like, 60+ years of people looking for efficient algorithms for all of NP and failing
Sort of. I at least understand those arguments and am willing to accept them as evidence that the likelihood of P=NP being proven in any given year is low, in the absence of known progress on attacking the underlying difficulty of any NP-hard problem.
However I’m more skeptical when these arguments are applied to other separations like NP vs P#P or NP vs co-NP because I doubt that any where near the same amount of effort is going into them due to their lack of direct practical applications.
I mean there are whole communities of researchers working on heuristics for several different NP-hard problems including, at least, SAT, ILP and TSP. Also some of these problems touch distinct branches of pure and/or applied mathematics like graph theory, the geometry of convex polytopes, algebra and non-linear optimization.
I don’t have a very clear idea of what a typical complexity theorist’s research consists of but my impression is that rather little of it consists of trying to find ways to collapse the classical complexity classes. I suspect this applies to P vs. NP as well but I think there are many non complexity theorists working on that problem, at least in some indirect way.
Comment #54 November 13th, 2020 at 5:37 pm
Gerard #53
“Find a short certificate that this circuit isn’t satisfiable” and similar questions are definitely sought-after …. they would be useful. If solved, it would imply NP = coNP, a much smaller implication than NP = P^#P. So, whatever probability you put on the latter, it should be less than the (low) probability of the former.
Comment #55 November 13th, 2020 at 6:00 pm
One thing I forgot to mention, “Fandom” (Formerly Wikia) would also be an option. It already runs Wikimedia, allows original research and is easy to handle. Aside from TV series and video games communities, some formal science communities are hosted there, like https://modeltheory.fandom.com/wiki/Main_Page .
I would be willing to look into uploading the content there – but only as a redundant side by side with for example the “less wrong” people.
Comment #56 November 13th, 2020 at 6:09 pm
Gerard #53: NP = co-NP would have practical applications. It would definitely be useful in many situations to have a short certificate of the non-existence of a solution.
But if you’re not already aware of it, you might want to read Some estimated likelihoods for computational complexity by Ryan Williams. It’s a fascinating article and he sometimes states some contrarian opinions. For example, he gives \({\sf NEXP} \ne {\sf EXP}\) only a 45% likelihood. He says that many will wonder why he attaches such a low percentage, and also says, “I suspect that others will, instead of wondering, just assume that I’m out of my mind.” His main reason is that we just haven’t studied \(\sf EXP\) enough to have any confidence about what its limits are.
Comment #57 November 13th, 2020 at 6:45 pm
G #54
> “Find a short certificate that this circuit isn’t satisfiable” and similar questions are definitely sought-after …. they would be useful. If solved
I think that to be practically useful you would need to be able to find the short certificate in P-time, which would imply P = co-NP = NP, a much stronger result than just co-NP = NP.
Comment #58 November 13th, 2020 at 10:56 pm
G #54, Timothy Chow: #56, Gerard #57: If there exists a polynomial-time algorithm that can be proven in (say) ZFC to decide (say) SAT, then any unsatisfiable SAT instance has a short proof in ZFC that it is unsatisfiable: for example, the proof that the solver decides SAT, followed by the complete runtime trace of the algorithm on the SAT instance of interest.
I strongly suspect that “there exists a polynomial-time algorithm that can proven in ZFC to decide SAT” and “P = NP is provable in ZFC” are equivalent in ZFC. However, Levin’s universal search implemented the naïve way (dovetailing over all possible algorithms, halting when one gives a satisfying witness) will literally run forever on any unsatisfiable instance, so we can’t get this equivalence trivially in the most optimistic way.
Comment #59 November 13th, 2020 at 11:52 pm
Gerard #54: No, that’s not really true. There are some problems that are important enough that we’re willing to do an exponential amount of work in a few cases to make sure that there’s no solution (e.g., a solution might correspond to a bug in an important piece of hardware or software that we’re trying to prove correct). We’d also like to be confident that the negative verdict of the exponential computation is really true, and is not a mistaken verdict caused by a bug in the computation. It would be really nice to have a short certificate that no solution exists, so that we can confirm the correctness of the computation much more cheaply than by re-running the exponential computation all over again.
Comment #60 November 14th, 2020 at 6:22 am
friend of the visually impaired #10:
Please translate your comment into French so that Francophones can access it. It is in fact embarrassing that you did not do so of your own accord.
Comment #61 November 14th, 2020 at 7:41 am
Timothy Chow #59
> There are some problems that are important enough that we’re willing to do an exponential amount of work in a few cases to make sure that there’s no solution
Can you provide an example of that ?
My impression is that most NP-hard problem instances of practical interest are not tiny and that except for trivial cases exponential time solutions are likely to exceed any available computational resources. It doesn’t matter how important a problem is if the observable universe doesn’t contain enough matter to build a computer capable of solving it and exponential solutions will hit that threshold very quickly.
Also in cases where an exponential computation is feasible you can typically enumerate the entire solution set and you have no need for any “short certificate” whether of satisfiability or unsatisfiability.
Comment #62 November 14th, 2020 at 8:40 am
Gerard #54
coNP certificates would be quite useful, I would think! (if they’re reasonably sized …. ϴ(N^24)-sized certificates probably wouldn’t see much use). Being able to search for a certificate will always be faster (by a constant) than trying all possible certificates, which is currently what you have to do to decide “true” on a coNP problem. There are other advantages, too: when searching for a certificate, you don’t have to keep track of your progress and restart if you lose your place. You can just have an algorithm trying certificates at random. Couple that with an algorithm trying NP certificates at random, maybe with some heuristic search on both, and I think you’ll get your answer much faster for large swathes of the problem-space.
It’s not polynomial time in the worst case, but that hasn’t stopped people from making SAT solvers up until now—I bet many of those systems could be improved by a negative certificate, up to a constant factor in the worst case.
Comment #63 November 14th, 2020 at 1:46 pm
Gerald #61
I know there is the Beckenstein Bound (T1) and Bremermann’s limit (T2) which should theoretically limit our ability to calculate in the physical universe to an arbitrary degree, but how confident can we be that the derivation from General Relativity and Quantum Field Theory used to get those theorems are actually true in nature? It’s seems like quite the bet. From the perspective of a non physicist, I think it’s the same kind of confidence in these theorems that particle physicists were willing to show towards low energy super symmetry. And despite there being mathematical derivations from Quantum Field Theory to derive weak SUSY, it turned out not to apply to nature. Analogous, I personally do not necessarily have high trust (> 95%) in any of those computational bounds T1, T2.
Even under the assumption that both theorems T1, T2 are true in the observable universe, is there still a way to achieve Super Turing Computation even with finite resources?
To generalize my statement above, even if we would have an axiomatic theory of physics as demanded by Hilbert in his sixth problem, I suppose it would be fairly easy to construct theorems which are derivable and as such part of the theory but irrelevant to the observable universe nevertheless.
Comment #64 November 14th, 2020 at 3:45 pm
Is there a possibility that there could exist some efficient algorithm that could only tell us whether an NP-hard problem has some solution vs has no solution, so that if there are some solutions, finding specific instances could still be inefficient?
Comment #65 November 14th, 2020 at 3:56 pm
fred #64: For NP-complete problems, the answer is no; indeed this is a classic homework problem. If you can merely efficiently decide whether solutions to NP-complete problems exist, then you can also efficiently decide whether solutions exist within some given lexicographic range. But that means that you can do binary search on the set of exp(n) possible solutions, in order to find an actual solution (if there is one) using only O(n) invocations of your decision algorithm.
Since you said “NP-hard,” I should add that there might be stuff above NP where the search/decision equivalence breaks down. Certainly there’s stuff below NP where it breaks down: for example, finding a prime factorization of a number or a Nash equilibrium of a game, for which the answer is always “yes, there’s a solution,” but finding a solution might still be intractable.
Comment #66 November 14th, 2020 at 4:41 pm
Scott #50
> And recall, NP≠coNP is already enough to imply NP≠P#P.
I’m having a hard time understanding why that implication holds. To prove that NP = P#P it should suffice to show that there exists an algorithm that can solve a #P-complete counting problem using a polynomial number of calls to an NP oracle. How does that imply the existence of a P-time algorithm to check the non-satisfiability of an NP instance, where you don’t get to use an oracle ?
Comment #67 November 14th, 2020 at 4:57 pm
Gerard #66: P#P is obviously closed under complement (i.e., it equals coP#P). So if NP=P#P then NP is closed under complement as well, QED.
Comment #68 November 14th, 2020 at 5:23 pm
Scott #67
Maybe my confusion is that my hypothetical proof would actually only prove that PNP = P#P.
I thought that PNP = NP, but apparently that’s not the case, hence the polynomial hierarchy and all that.
Comment #69 November 14th, 2020 at 7:21 pm
Gerard #68: Right, PNP contains NP, coNP, and all sorts of problems involving Boolean combinations of NP queries. If NP=PNP, then once again, NP=coNP and the polynomial hierarchy collapses to NP.
If PNP=P#P, then again the polynomial hierarchy collapses, in this case to PNP. Here, though, the reason is Toda’s Theorem, that PH⊆P#P.
Comment #70 November 14th, 2020 at 7:32 pm
Gerard #68, Scott #69: Wait, don’t we have \(P^{NP} = NP\) trivially? (The NP witness for a P^NP problem would be the complete runtime of the P^NP algorithm on the instance of interest, combined with appropriate NP witnesses for every call to an NP-complete oracle.) I’m assuming that you meant to write about NP^NP.
G #54, Timothy Chow: #56, Gerard #57, duck_master #58: I wrote this comment earlier to point out that if we assume (a strong form of) “\(P = NP\) is provable in ZFC”, then we get short coNP witnesses for free.
Comment #71 November 14th, 2020 at 7:45 pm
duck_master #70: Nope. What if the answer to an NP query is “no, there’s no solution”? What’s the NP witness for that?
What’s true, and basically by the argument you gave, is that PNP∩coNP=NP∩coNP.
Comment #72 November 14th, 2020 at 8:08 pm
duck_master #70
The easiest way to see that P^NP is stronger than NP (if NP != coNP) is to imagine solving a coNP-complete problem, like “this circuit is not satisfiable”. You could run an NP oracle, and then you (in P) can invert its answer. This problem is thus in P^NP, and since it’s not (yet known to be) in NP, NP ≠ P^NP.
The problem with your “program trace” idea is that either oracle output is equally convincing to you (if you don’t have an algorithm for solving NP problems in P) … you could write “the oracle returns 1, and then the machine output 0” OR you could write “the oracle returns 0, and then the machine output 1”. Both are valid program traces, so since one gives a “yes” answer, this NP algorithm will always output “yes”.
Comment #73 November 14th, 2020 at 8:18 pm
Scott #2. I don’t don’t think this is something you can fix *just* with a team of legal eagles. The settlement basically says, if you’re making this available to the public, you have to make it available to the disabled as well. Like you, I find this infuriating. I’m recording lectures for my Advanced Algorithms class and posting them on YouTube for my (remote) class. I’d be happy to make them publicly available, but I can’t because of the settlement: if I make the publicly available, they have to be captioned. And Youtube’s automatic captioning isn’t good enough: someone has to pay real humans to do it. So it feels like I’m being prevented from making my little contribution to education.
But then I step back and think: what is the ethical angle here? Suppose I figure out something that I am really motivated to share with the world. Without a settlement, lazy person that I am (as proven by 20 years of missed opportunities) I’ll share it the way I always do and the disabled will miss out. But with the settlement, my strong motivation to share will *also* cause me to make it accessible so everyone can benefit.
So there’s a tradeoff. Sure, less of our work gets shared overall, but more gets shared accessible. So basically we’re “taxing” our knowledge production, taking some of it away from the abled in order to provide more of it to the disabled. Which is a typical approach to maximizing fairness.
Comment #74 November 14th, 2020 at 8:58 pm
Hmm, I am just gonna sit there and witness the miraculous scene that my favorite computational ‘mathy’ philosopher coolly, easily defeated every confident challenger. It humors me.
P.S.
I am learning some basic mathy-philosophy materials from various sources that interested me,
Is it okay your next podcast with lex or someone else, could be some topics, perhaps, related to the philosophers or ideas you liked, believed, reformed, during your growth, how it influence and form your personal belief, personality, and influence your personal research philosophy?
(I don’t know how to form my questions, exactly, sorry, I understand different people have different “ways” or some kind of operating system in their minds, I could tell that I have not rigorously trained or others ‘bugs’ or potential weakness in my logic.
I am trying multiple approaches and trying to form a one that suitable for me)
please consider if it is okay to be straightforward to younger students
Thanks for reading, sir
Comment #75 November 14th, 2020 at 10:09 pm
David Karger #73: Yes, I understand the “reasoning.” My claim is that this is an absolutely terrible (even transparently idiotic) tradeoff. When an academic resource is available for free online, it’s not just that millions can benefit from it. Rather, it’s that others can then improve the resource—for example, by adding captions, or translating it into other languages—thereby making it accessible to more and more people. Whereas the other approach, as you’ve seen, leads to no one having access.
Fairness is just one value: a fine value, but it doesn’t get an automatic override of every other human value.
A similar story seems to repeat itself with every new medical treatment, in fact every worthwhile new thing of any kind (computers in schools, broadband Internet…). Again and again, people fret about whether the thing needs to be stopped, because it’s unfair that it creates a divide between haves and have-nots. I’m with the economists here: if the thing is good, then just let it proliferate. At first, maybe only the rich will have it. But once demand becomes clear, the supply goes up, the price drops, and eventually >90% of the population has access to the new thing … whereas the “fair” approach would’ve led to 0% having access to it.
Or here’s a closer-to-home example: suppose an observant Jew is coming to an academic conference, and suppose the organizers try to find kosher food, but they can’t do better than unappetizing rubber airplane chicken. Should the whole conference therefore be cancelled? Indeed, should it be cancelled even prior to any actual observant Jew registering, because the fact that one might want to come creates an inequity? Hopefully we agree that that would be loony!
(Man, I actually miss conferences…)
I want to live in a society where we try hard to accommodate special needs whenever we become aware of them. But a society where everything gets held hostage to special needs—or worse, to some bureaucrat’s idea of what a future hypothetical person’s special needs might be, which might differ substantially from the actual special needs that will later present themselves—seems like a cruel caricature of that world.
Comment #76 November 14th, 2020 at 10:29 pm
@scott
Sir, I am refreshing my page at the speed of 10 seconds once waiting for your response, after seeing your comments #75…
If I asked something improper, please shoot me a personal email to remind me or scold me cruelly, publicly in your blog are both okay…
say something…
Comment #77 November 14th, 2020 at 10:45 pm
“Ms. BLUE” #76: Sorry, I had some trouble figuring out what your question was (assuming you’re the author of #74). If you want to know about what influenced me philosophically, though, you might enjoy this interview.
Comment #78 November 14th, 2020 at 10:53 pm
Wow! Thanks ( I really should change the keyword of searching, can’t believe I miss this interview)
Comment #79 November 14th, 2020 at 11:23 pm
Scott #71, G #72: Thank you for the clarification! I need to pay more attention in my computational complexity proofs.
1Zer0 #63: If an object that violated the Bekenstein bound existed, then one could destroy physical information by throwing this object into a black hole. Similarly, if an object that violated Bremermann’s limit, then it would also violate the Heisenberg uncertainty principle. None of this requires QFT or anything like it; only a very vague understanding of GR and the formalism of quantum amplitudes, respectively.
Comment #80 November 15th, 2020 at 2:31 am
Hi everybody, I am glad to see that the Zoo found new hosts. Regarding the discussion and the accessibility dilemma: (Especially, David #2, #73, Scott #3, #5, #75)
First , the anti-bureaucrats sentiment and rhetoric is not clear in this case. One needs to make a general policy and I don’t see why it matters if the policy is made by philosophers, academics, politicians, or people who hold administrative jobs (aka bureaucrats). I certainly don’t see justification for the statement: “bureaucrats at a higher level who suffer from an impairment far more serious than blindness, deafness, or anything else that’s merely physical.”
Second, when it comes to accessibility for the disabled, the economic incentives are clear: If you do not enforce accessibility it would simply not happen. In this case, the outcome seems reasonable: Publicly supported entities will need to put money to make content that they regard important accessible. For other content, like the Zoo or David’s online lectures, the owners themselves will have to decide what to do with them.
Comment #81 November 15th, 2020 at 2:54 am
IIUC, the regulation applies to any organization or person who has an employee in Ontario.
That’s pretty broad, but presumably an individual hosting the Complexity Zoo as a personal project wouldn’t be legally required to meet the accessibility requirements? Though with a fine of up to $50,000, not sure i would take a chance.
BTW, assuming i looked at the right version of the regulation, it specifically mentions organizations in the education sector.
And i can understand that, because of how critical education is.
On the other hand, it should probably only cover required course material, rather than just anything on an edu site, even at the cost of more legalese.
As it is, it’s basically taxing any charitable contributions to the wealth of educational material on the web by the people who are best qualified to do so. Actually, I’ve used John Watrous’ UWaterloo site to learn about quantum computing, among several others.
Can we not leverage AI to make better accessibility tools? It’s pretty archaic to have to manually annotate web pages for accessibility.
How unfortunate that there’s finally a $50,000 penalty for hosting a site with horizontal scrolling, and it’s not an undisputed step forward.
Comment #82 November 15th, 2020 at 10:33 am
duck_master #79
You are right, Bremermann’s limit is actually reasonably simple to derive, I read through his original paper. This increased my confidence in Bremermann’s limit to 99.7%. Violating Heisenberg’s uncertainty or the mass energy equivalence seems to be gross and the constants are, as far as I am informed, to the best of our understanding, presumed to be the same in the observable universe. Still, a mathematical derivation alone without an experimental verification is just that – a logical possibility for the Bremermann’s limit theorem to also apply to nature.
The Beckenstein Bound’s derivation is beyond my understanding of physics and loss of information seems to imply, according to the wiki page on the BH information Paradoxon, the violation of unitarity. Unitarity is apparently taken as an axiom in QM although some physicists appear to toy around with violations to unitarity. I suppose assuming non unitarity leads to undesirably other consequences in QM. Once more, a mathematical derivation alone without an experimental verification is just that – a logical possibility for the Bekenstein Bound theorem to also apply to nature. So I trust the experts have good reason to assume it to be realized in nature but personally I can’t put more than 50% confidence into it.
Comment #83 November 15th, 2020 at 11:02 am
Gerard #61: I already gave an example. Google something like “sat solver formal verification” for more details. Formal verification of the correctness of a piece of hardware or software can often be reduced to verifying that a particular instance of SAT or constraint satisfaction has no solution. If people’s lives could depend on absence of a solution, we might be willing to invest—oh, I don’t know—maybe a million core-weeks making sure there’s no solution. It would sure be nice if confirming the correctness of the calculation took only (say) one core-day.
Comment #84 November 15th, 2020 at 11:33 am
Gil Kalai #80: My working definition of a “bureaucrat” is anyone who decides on policies like this one—even in the relatively rare case that they happen to have a PhD in physics or math.
Opinions like yours are why for now I’ve chosen LessWrong, a private entity, to host the Zoo. I’m worried that, on any publicly supported server, it will soon be impossible to host any product of individual effort or creativity that doesn’t have legal, compliance, etc teams behind it.
Comment #85 November 15th, 2020 at 2:28 pm
Scott (#83), Indeed you have made a good choice for a host.
Regarding accessibility, I do not know the situation in Ontario, but the MIT-NAD Agreement that David (#2) referred to ( https://accessibility.mit.edu/captioning/mit-nad-agreement ) seems reasonable. The central effect of this agreement will probably be of making free academic content much more accessible to the deaf than before. Individuals who use MIT server to present a product of their effort or creativity will get some instructions and assistance on how to make them accessible.
Comment #86 November 15th, 2020 at 3:07 pm
David Karger #73: Maybe some of your 854 students would want to transcribe your lectures as their final project? Or maybe it could be a UROP?
Comment #87 November 15th, 2020 at 3:15 pm
who from within iqc told you to move? was it the communications team? someone just brought this up so give us a lil time to work this out.
Comment #88 November 15th, 2020 at 3:16 pm
Gerald #54, people use exponential-time algorithms in SAT solvers on huge SAT instances all day long in all kinds of applications. The trick is that exponential refers to the worst case over all possible instances. For the instances that come up in practice (say in CAD layout), the algorithms usually are tolerably fast. There is a big research literature about this, and various practical guides. Here is one that I like: https://yurichev.com/writings/SAT_SMT_by_example.pdf
Comment #89 November 15th, 2020 at 3:34 pm
i also want to mention that accessibility compliance is a serious constraint, to the point that government funding to iqc can be stopped if we do not comply. scott: can you pm us a lil more info on the correspondence between you and iqc?
Comment #90 November 15th, 2020 at 3:46 pm
“Must be captioned (or removed from public view) as soon as practicable”
Wondrous for hearing equality. Disastrous for educational opportunity equality.
Comment #91 November 15th, 2020 at 5:00 pm
Scott, does anyone still update or maintain the complexity zoo? I’ve noticed that important classes such as exists-R and CLS appear to be missing entirely. (I don’t think I’m the right person to add them, though…)
CLS has occurred in the titles of several recent papers:
https://arxiv.org/abs/1702.06017
https://arxiv.org/abs/1802.07702
https://arxiv.org/abs/2011.01929
exists-R is important enough to have survey-like papers written about it:
https://drops.dagstuhl.de/opus/volltexte/2016/5718/
These are not obscure classes!
Comment #92 November 15th, 2020 at 6:32 pm
One can now, with hindsight, potentially argue that the Ontario regulations did lead the complexity zoo to switch faster than it would otherwise have. Similarly, had SB5 passed, widespread job losses would not have been the only outcome. All economic actors would have changed their behaviors. ‘The end of laissez faire’ by Keynes is imho the best essay on the balance between individual rights and government regulation.
Comment #93 November 15th, 2020 at 7:14 pm
Scott, to clarify as you didn’t make a statement in that regard yet, would it be advisable to additionally create a complexityzoo.fandom.com wikia? Just as an alternative/ backup to sync.
Comment #94 November 15th, 2020 at 7:29 pm
asdf #88
> Gerald #54, people use exponential-time algorithms in SAT solvers on huge SAT instances all day long in all kinds of applications. The trick is that exponential refers to the worst case over all possible instances.
I assume you were trying to respond to my comment #61 though you misspelled my name and comment #54 wasn’t from me.
I wasn’t referring to heuristics but to brute force algorithms, which is what I think the comment I was replying to was about, because it talked about doing “an exponential amount of work”. which heuristics normally try to avoid.
Comment #95 November 16th, 2020 at 12:08 am
Regarding accessibility laws/regulations (David Karger #73, Gil Kalai #80):
I think Kelsey Piper gets it right in this pair of posts. As a general rule, if the government wants X to happen, it should directly do X, rather than passing laws requiring anyone who does Y to also do X. Taxation still has to happen somewhere, obviously, but now what’s being taxed and what’s being done are decoupled from one another, which is useful.
In this case, doing X directly isn’t exactly practical, but we can still do our best to apply this principle. That is to say, if the government wants to require all existing online university content to be made accessible, it should, say, reimburse the universities for the expense, or (if we want to be slightly more direct) hire accessibility experts and send them to the university. Something that’s of that form, that meest the principle that if it wants something to happen it should pay for it to happen.
(Also, I suspect James Babcock #13 or Mitchell Porter #33 may be right here about why this is happening. It’s worth keeping in mind that when you institute a new rule, the costs do not fall only on those not compliant with it, but also on everyone who needs to verify their compliance with it; and that just because you’re following the rule, doesn’t mean you’re following the rule in a way that those checking it can see, so additional costs come from that…)
(Also, what the hell is up with the date in the comment preview? It seems to think that the current year is 4564…)
Comment #96 November 16th, 2020 at 6:13 am
1Zer0 #93: You’re welcome to do that. My only worries are
(a) that it would get out of sync with the main Zoo if someone actually updates the latter, and
(b) that the Zoo having a “fandom.wikia.com” URL might encourage the misconception that we study SZK and AWPP for the same reason others study Stormtroopers and Ewoks! 😀
Comment #97 November 16th, 2020 at 6:15 am
Shalev #91: As far as I know, no one has made significant updates in a long time. ExistsR and CLS would both be excellent additions! Why aren’t you the person to do them? 😀
Comment #98 November 16th, 2020 at 7:54 am
Gerard #94: I am not sure exactly what you mean by the terms “heuristics” and “brute force algorithms.” Most SAT solvers use “heuristics” in the sense of techniques that often (but are not guaranteed to) speed up computations enormously in practice, and so are not usually described as “brute force” (which to me connotes naïvely exhausting over all possibilities). On the other hand, they are guaranteed to give the right answer eventually, and they take exponential time in the worst case.
Comment #99 November 16th, 2020 at 10:09 am
vn #92
But the zoo isn’t getting any more accessible, just switching to a different host … in fact, I think it’s still unclear what exact accessibility changes are needed (Reread the paragraph “Nearly a score years ago,….”). The move seems to be primarily CYA-based, which is how a lot of regulation with bad incentives ends up shaking out in the end (agree to any Cookies, lately?? :P).
The zoo is just being laboriously moved to another site, which strategy—while potentially as costly in resources as making whatever specific changes were demanded—has the benefit that, no matter how wrongly it might go, no one will be slapped with a $100,000 CAD fine for messing it up.
Comment #100 November 16th, 2020 at 10:38 am
Sniffnoy #95
Agreed 100%
For content before 2019, the MIT-NAD settlement says:
This gives me the idea for a new system: the government creates a Bureau of Accessible Media. A member of the public who wants a video or a series of videos “accessibilized” can file a request with this Bureau containing a link to the content. The Bureau retains contractors who do the work of downloading the video file(s), transcribing captions, and producing A) a universal .SRT file(s) containing the caption data and B) a copy of the video file(s) with the captions superimposed.
Then, the big government organization reaches out to the video owner and says “upload this, too, or add these captions to the video player, or else then you will be in violation”.
It puts the most egregious time/monetary costs exactly where they should be—on society—and it imposes a trivial burden on both disabled people and educators.
Comment #101 November 16th, 2020 at 1:46 pm
Timothy Chow #98
By “brute force algorithm” I just meant exhaustive search, which is what I thought you meant by algorithms that do an “exponential amount of work”. Heuristic solvers go to great lengths to avoid doing exponential work and the instances on which they do end up doing that are essentially failures because the program either hits a predetermined timeout or tries to run for what is effectively forever and inevitably gets terminated at some point.
Yes, I agree that a short certificate of unsatisfiability would be useful to heuristic SAT solvers, but I couldn’t see how the kind of algorithm I had in mind could provide that in any useful way. The whole discussion on co-NP got started as a tangent to my original question because I initially didn’t understand the distinction between NP and PNP, which depends on the details of how NDTM’s and their time complexity are defined. Without that distinction the difference between NP and co-NP would disappear because PNP contains them both.
Comment #102 November 16th, 2020 at 4:18 pm
Hi Sniffnoy (#95)
1) I do not agree with your general X, Y rule. In the site that you referred to the main example was minimum salary. A large majority of economists including those leaning to the right, support minimum wages and all welfare states have minimum wage laws, including the US. (I also support the 1% for art law but this is a more complex matter.)
2) When it comes to accessibility, your X, Y rule does not even apply because the basis of the accessibility laws is the principle of no discrimination. So if, in the eyes of the law, MIT or Harvard discriminate against a certain group, this violates the law and the remedy is not just for the government to give an alternative service for those discriminated against, but rather to stop the discrimination.
3) Of course, we have some tradeoff here and we need to assess it. But look at our case: Scott A. was unhappy that his site is no longer supported by IQI as he wrote about on November 12th, 2020 at 1:10 pm. Two hours later, on November 12th, 2020 at 3:16 pm, an alternative host was offered and by November 14 a deluge of serious hosting offers were available.
Now, imagine Scott B. who was unhappy in 2012 or 2014 or earlier for not having access to MIT or Harvard material. What could make Scott B. especially unhappy is that MIT and Harvard are very rich, non profit organizations, publicly supported in various ways, and on top of that, committed (by their own declarations decades ago) to values of accessibility and non-discrimination. Nevertheless, it takes a lawsuit and 5 years of negotiations to force MIT and Harvard to comply with the law (and their own ideals).
So (with some amount of exaggeration, not uncommon to this site) we can say that two hours and sixteen minutes divided by 5-8 years, roughly 1:5000 is the tradeoff.
4) So, at the end, I find myself agreeing that the bureaucrats who handled the accessibility issue at MIT, Harvard, and possibly IQI, suck. (I still object to comment #3’s rhetoric.) But my reasoning is different from Scott’s. MIT and Harvard shouldn’t have waited to be forced before acting on this matter.
Comment #103 November 16th, 2020 at 4:36 pm
G #99,
It’s also worth pointing out that, given the choice of making the zoo more accessible vs making it inaccessible, the University of Waterloo chose to make it inaccessible, which is exactly the concern with how this regulation is implemented.
In terms of accessibility upgrades, i don’t think you need to go much further than upgrading MediaWiki, or at most filing a bug. It’s not like the Complexity Zoo is using custom extensions right?
That’s actually what’s striking about this case: the zoo is relatively easy to make accessible. For some sites, accessibility requires abandoning or reimplementing whole features.
Plus, the University of Waterloo does have the resources to make it happen, whereas other organizations or individuals might not. Presumably, they’re just not prioritizing the site relative to all of the other content that they host and which also needs to be updated.
In my experience, whenever the maintenance cost of hosting a site begins to require active intervention rather than passively paying a recurring fee, that’s when you start shedding and shutting things down.
Comment #104 November 16th, 2020 at 6:25 pm
Gil Kalai #102,
Sure, but the question remains, what kind of action would they take?
Because you can either make the content sufficiently accessible (merely AA rather than AAA) or inaccessible, by some deadline.
And if it takes “a lawsuit and 5 years of negotiations” to even prompt some action, why expect the former?
Keep in mind that the zoo is already fairly accessible, in terms of support for text-scaling, high contrast and even a screen-reader. It just hasn’t been properly reviewed and tweaked for the required AA rating.
It’s not like the University of Waterloo chose to shut down a site that was in egregious violation of accessibility standards. It just happens that reviewing and tweaking a site for accessibility certification requires manual intervention and that raised the maintenance cost of the complexity zoo to more than they are willing to cover.
My opinion is that everyone benefits from accessibility compliance. Not just in the form of improved usability (no horizontal scrolling, sensible navigation menus, etc), but because everyone is at risk of being disabled, even if just temporarily.
But that doesn’t mean that we shouldn’t be careful about how this type of regulation is implemented. If universities are choosing to shut down semi-inaccessible educational sites then this is a step in the wrong direction.
Comment #105 November 16th, 2020 at 8:39 pm
Gerard #101: I understand that it was a tangent, but I think it’s a very interesting tangent!
You expressed doubts that people have put much effort into trying to prove that NP = co-NP because you thought it wouldn’t have practical applications. I’m trying to explain that if we were able to figure out a general method of obtaining short certificates for problems in co-NP, then that would be of great practical value, period, not just “useful to heuristic SAT solvers.”
As matters stand today, in many cases the only way we know how to verify that a certain crucial piece of software has no bugs is to run an extremely long computation—and if you don’t trust the computation fully, then the only thing you can do is to run another extremely long computation. If we had a proof of NP = co-NP then in all probability we would just have to run an extremely long computation once, to find a short certificate of unsatisfiability, and then to make sure that the computation was correct, we would just have to run a very fast and simple computation to validate the certificate.
Comment #106 November 17th, 2020 at 1:54 am
Not all visually impaired people use screen readers. In my own (very mild) case, my preferences are (in this order):
1. That the Complexity Zoo continues to exist and to be available on the public internet.
2. That it’s readable with reasonable text size and no horizonal scrolling on a small screen, such as that of a mobile phone.
3. That there’s an option to read it as dark text on a light background.
4. That no information is conveyed solely by the blue part of RGB colour-space.
Some notes on these:
Gil Kalai #80:
Why?
LibriVox is a massive counterexample to this statement.
Comment #107 November 17th, 2020 at 4:39 am
As a suggestion, quantum computers solving NP-hard problems could be added to https://en.wikipedia.org/wiki/List_of_common_misconceptions, it is so universal.
Comment #108 November 17th, 2020 at 8:26 am
I’m deaf, and for my whole life I have been asking people to caption videos and to provide services X and Y, etc. I am supportive of allowing people to put lecture videos online first and then getting human-provided professional captions upon request (but if there’s no request, then I say, who cares, leave the video online…).
However, I also have some conflicting feelings because when I ask people to caption videos, or for conferences to provide this or that, it’s usually not going to be done at all, or will be done at low quality, or will require endless email exchanges, so in that sense I’m happy there was a lawsuit to raise attention to this issue, especially for a university like MIT. From reading Gil Kalai #102, I think I mostly agree with the post.
YouTube/Google captions are getting better, and I’m able to use Google Meet captions and function well in virtual meetings. I’d be supportive of having a test of automatic versus human-provided real-time captions, and then allowing videos to use automatic captions once a performance threshold is exceeded. I’m not sure if such an automatic vs human test exists.
Comment #109 November 17th, 2020 at 10:19 am
Daniel Seita #108: Thanks for sharing! I’d remark that every time you succeed in getting a video captioned, you’re providing value not only for the deaf, but for all of us who find reading easier than listening. (It’s analogous to how ramps in buildings are a huge benefit not only to the wheelchair-bound, but to parents with strollers too.) I’m thrilled that automatic captioning (which I often turn on myself) has improved so much recently.
Comment #110 November 18th, 2020 at 10:23 pm
On a note closer to the original post, I have two suggestions for improving the Complexity Zoo, one non-radical* and one radical:
– The non-radical suggestion is to make a page for each complexity class (in the style of Wikipedia), condensing the glossary into links and bare definitions.
– The radical suggestion is to make a “formal double” of the Complexity Zoo where every claim or definition about complexity classes that is asserted informally is proved formally in some standardized formal proof language.
*what’s a good synonym for this? I can’t think of one right now.
Comment #111 November 19th, 2020 at 7:51 am
Scott #75, I used to believe the argument you make. But then began reflecting on where it ends. Suppose a restauranteur told you that installing a ramp to provide handicapped access would force them to sacrifice two tables, thus decreasing capacity and causing more non-disabled individuals to *lose* access than the number of disabled people who would gain it. Does that absolve them of responsibility to accommodate the disabled? It’s relatively rare that providing an accommodation has no downside.
On a more practical note, here’s one idea for you: see if the people who run acawiki (https://acawiki.org/ ), dedicated to making academic scholarship more broadly available, would be willing to host your pages as a subproject.
Comment #112 November 19th, 2020 at 3:21 pm
David Karger #111, Scott #75: In a way it is too cheap to allow to cancel an academic resource resource completely instead of making it accessible. This only allows for blame shifting without improving anything. Maybe allow to cancel 50% of the academic offering, if 50% of the remaining academic offering is made as accessible as requested. Then all sides would have a fair share of the burden. You can also shift the numbers, like requiring to make at least 95% off the remaining academic offering accessible, or allow to cancel up to 80% of the offering. The point of those cutoffs is just to prevent the easiest blame shifting loophole anyway, so allowing to cancel more can be fine (and avoids that you are penalized too much for being nice in the past), especially since the current situation allows to cancel everything.
Comment #113 November 19th, 2020 at 3:53 pm
gentzen #112: Or how about not canceling anything—just building more and more resources and making them more and more accessible?
I like to keep it simple.
Comment #114 November 19th, 2020 at 5:33 pm
My question is how to prevent the blame shifting loophole. Better keep it simple, I agree, otherwise it will only create even more loopholes. No pure regulation will prevent all loopholes, at least not without explicit help by common sense. So the regulation must somehow make it clear that simply closing down access for everybody is against the intention of the regulation. However, it should still be OK to close down access sometimes, but not at a rate much higher as would have occured without the regulation.
But I failed to answer my question. Random numbers like 50%, 80% or 95% are not helpful, because they give a false sense of detail, which will often not be helpful in concrete cases.
Comment #115 November 21st, 2020 at 4:42 am
I think that something is missing in the discussion about accessibility. Yes in the short term this causes harm to somethings. However, it puts pressure on everyone to make sure that whatever they will create in the future it will be accessible. In particular, it means that new technologies will be created to make things more accessible. Also, of course organizations will have to invest resources to make sure everything new is accessible.
Comment #116 November 23rd, 2020 at 9:57 am
Scott #113 it’s really easy to say “how about we just keep doing what’s convenient for us and let someone else do the accessibility.” And then nobody does.
Comment #117 December 2nd, 2020 at 1:10 am
(Sorry, finally getting back to this)
Gil Kalai #102:
1. Without further context I’m not sure how seriously to take that. In particular we must remember the appropriate comparison here. Applying Piper’s principle here, it would say that, instead of a minimum wage, one should have wage subsidies or UBI. Do you disagree that these would be superior options? If a bunch of economists were merely asked whether they’d support minimum wage, without an alternative being offered, the results may be hard to interpret. (E.g., some may imagine an alternative of UBI while some may imagine an alternative of nothing, resulting in fairly worthless results.)
2. I’m not sure how you can say it doesn’t apply when it’s a clear example — they’re saying if you provide something, then you must make it accessible in the following way. You can certainly claim it is also an example of nondiscrimination, which I would disagree with, but I don’t see that as particularly relevant because it’s clearly an example of this sort of conditional mandate regardless of what else it may also be an example of.
Your points (3) and (4) don’t address the question at all. To the blind person getting the accessible versions they require, it’s not particularly relevant whether the university or the government pays for it. But the latter option is superior because it means that said accessibility necessarily happens, whereas the former means that there’s a chance it happens and a chance it becomes accessible to nobody instead. Nothing in (3) or (4) does anything to argue against Piper’s principle that I linked.
Comment #118 December 14th, 2020 at 7:29 am
My two cents on the “Wikimedia” point, in particular in relation to the comments of @Victory Omole and @Jon Awbrey, and on the suggestion of using Github Pages by @duck_master.
With some colleagues, we created some time ago the Complexity of Games Compendium (CoG), which focuses on computational hardness results for games and puzzles: https://www.isnphard.com/
We are hosting it on Gitlab Pages.
The hosting is free, but contributing requires basic familiarity with Git. However, it was a very natural choice in order to be able to host playable implementations of the complexity results.
Regarding CoG, I did consider myself the possibility to move the part describing the results as a Wikiversity projects, while maintaining external links to “playable reductions” hosted on Gitlab. Wikiversity appears to be intended for exactly this kind of use. Of course, the moving would take some effort… I’m writing this mainly to advertise the Wikiversity option for people that want to start similar projects.