Tuesday, March 28, 2006

Science Without Borders

Berkeley complexity theorist Luca Trevisan travels to China and you can read all about it in his new weblog In Theory.

But suppose you couldn't. A Slashdot reader asks What would we lose from a regionalized Internet?

If the internet was separated into regions, how much would you lose? How often do you visit other countries' web sites? How often do you e-mail people in other countries? What would foreigners lose by not being able to visit US-hosted sites, and how quickly would they be able to recreate what they lost? What other process that we are not normally aware of depend on a borderless internet?
As an academic an international internet has gone from being a useful tool to a critical part of scientific progress. Yesterday alone I had four conversations with different scientists abroad on topics like collaborations on conference and journal papers, conference organization and recommendation letters. Many of my co-authors live abroad and my research would greatly suffer if I could not so easily communicate with my colleagues. Right now I can collaborate with a researchers in Israel as easily as one in New York.

Beyond that I download papers off of researchers homepages abroad and they download my papers from mine. Archive and online journal sites would have to be sychronized on different parts of a separated internet, a difficult task to maintain. Tools like Citeseer which seek out online papers would not function as well. And many of you would not be reading this post—Nearly a third of the readers of this weblog reside outside the US. And how would Luca write to us from China about his travels there?

Speaking of Slashdot, Zeev Dvir writes

Just wanted to let you know about the current Slashdot poll on whether P = NP. The comments are hilarious.


  1. Great point. The best thing (at least for me) is the internationalization of the internet.

    China Law

  2. The comments to the P=NP poll are much more sad than hilarious. Someone decided to "explain" what P and NP are and wrote: "NP stands for the set of problems that can't be solved in polynomial time. These problems take an exponential amount of time to solve, so usually can't be solved within a reasonable amount of time by a computer." I wonder what is it about this problem that makes it so hard for people to understand correctly?

  3. it's not so strange that people get the definition of NP wrong; "non-polynomial" is much more natural as a first guess than "non-deterministic polynomial," I suppose. the weird thing is that they don't immediately conclude that P=NP is tautologically false. this post in particular goes on to say that if P does equal NP, then the world would change... (disappointingly, he doesn't mention that I will be the new pope.)

  4. Should we change the name of
    NP to NDP so that
    people cannot easily
    take it as

  5. I might be better to call it P vs PV. Polynomial versus polynomially verified. Verifiers are a much more useful concept today than when Sipser's book was being written, and it helps to understand the newer techniques.

    As for borders, just look back to the Cook Levin Theorem. Many today seem to call it "Cook", but Levin's results behind the iron curtain show how much is wasted if we are separated from communication.

    To really remove the borders, all scientific research should be done in English, so more obscure results won't be missed. (I agree that any single language would be good... but English is the only language in use today that can be expressed in 7-bit ASCII, so there's that. And yes, I'm being sarcastic in that there are much better reasons to pick English anyway.)

  6. it's not so strange that people get the definition of NP wrong; "non-polynomial" is much more natural as a first guess than "non-deterministic polynomial,"

    The acronym NP is just the worst possible name some could come up with to describe "Non-deterministic Polynomial" when P is defined as "Polynomial". At the very least, it should be P vs NDP if not something else.

  7. Maybe the worst thing about the P vs NP question on slashdot is that the meaningless answer "undecidable" is included in the list (let alone the fact that it is currently winning).

  8. In Theory has all the makings of a fabulous blog!

    Check out the latest entry for an amusing take on the internetionalization from the other side of the Great Wall...

  9. We should find P versus NP in logic view actually my friend and I have already been learning first order logic and second order logic--another beautiful science.

    Computer theory Scientist have already proved some relationship between P, NP and second logic.
    And we believe we can go further.

  10. I've heard it suggested that we should try to keep doing math in different languages as it gives somewhat different perspectives for looking at something. However, most people I've seen advocating this position are native French speakers...