Ernie's 3D Pancakes

A partial list of things milk is not supposed to taste like

1. Bandaids.

Free (as in beer) speech

Exhibit A:

"I'm sorry, but on 'compelled speech,' nobody thinks that this law school is speaking through those employers who come onto its campus for recruitment," the chief justice said. "Nobody thinks the law school believes everything that the employers are doing or saying."

The lawyer adjusted his focus. The law schools have their own message, "that they believe it is immoral to abet discrimination," he said.

This time, Justice Sandra Day O'Connor took issue. "But they can say that to every student who enters the room," she said.

"And when they do it, your honor, the answer of the students is, we don't believe you," Mr. Rosenkranz said.

"The reason they don't believe you is because you're willing to take the money," Chief Justice Roberts interjected. "What you're saying is this is a message we believe in strongly, but we don't believe in it to the detriment of $100 million."

Exhibit B:

"I was headed to the cafeteria for a cup of coffee; why didn't I just keeping going?" Klocek said. "I don't know. But if militant Zionists had been there, I might have engaged them too. Being a truth seeker means being a loner."

When the students complained to Klocek's dean, she and other administrators apologized profusely to them. She called in Klocek separately and suspended him, with pay, for the semester. She also noted of his 14 years at DePaul: "Never during that time have we experienced a situation in which he lacked judgment, abused his position as a teacher to force his ideas upon students or treated students with disrespect." [...]

"I'm not the ideal poster boy," Klocek said. "But freedom of speech is a cause worth fighting for."

DePaul's president agrees.

"I get accused of being against free speech," Holtschneider said. "But freedom of speech for students requires they have a professor who treats them with respect."

Klocek's attorney, John Mauck, is representing him on a contingency basis: He doesn't get paid unless Klocek wins. Mauck said he took the case because members of his firm, evangelical Christians, have a philosophical commitment to freedom of expression.

Exhibit C.1 [pdf]:

Throughout the trial and in various submissions to the Court, Defendants vigorously argue that the reading of the statement is not “teaching” ID but instead is merely “making students aware of it.” In fact, one consistency among the Dover School Board members’ testimony, which was marked by selective memories and outright lies under oath, as will be discussed in more detail below, is that they did not think they needed to be knowledgeable about ID because it was not being taught to the students. We disagree.

Dr. Alters, the District’s own science teachers, and Plaintiffs Christy Rehm and Steven Stough, who are themselves teachers, all made it abundantly clear by their testimony that an educator reading the disclaimer is engaged in teaching, even if it is colossally bad teaching. See, e.g., Trial Tr. vol. 6, C. Rehm Test., 77, Sept. 28, 2005; Trial Tr. vol. 15, Stough Test., 139-40, Oct. 12, 2005. Dr. Alters rejected Dover’s explanation that its curriculum change and the statement implementing it are not teaching. The disclaimer is a “mini-lecture” providing substantive misconceptions about the nature of science, evolution, and ID which “facilitates learning.” (14:120-23, 15:57-59 (Alters)). In addition, superintendent Nilsen agrees that students “learn” from the statement, regardless of whether it gets labeled as “teaching.” (26:39 (Nilsen)).

Exhibit C.2 [pdf]:

To be sure, Darwin’s theory of evolution is imperfect. However, the fact that a scientific theory cannot yet render an explanation on every point should not be used as a pretext to thrust an untestable alternative hypothesis grounded in religion into the science classroom or to misrepresent well-established scientific propositions.

The citizens of the Dover area were poorly served by the members of the Board who voted for the ID Policy. It is ironic that several of these individuals, who so staunchly and proudly touted their religious convictions in public, would time and again lie to cover their tracks and disguise the real purpose behind the ID Policy.

Exhibit D:

I've been telling prospective graduate students for years that the distinctive strength of Chicago political theory was its pluralism. [...] That's good for the students; and it's good for us. I was shocked by the self-study's endorsement of a different path long before I realized its consequences for my employment. It seems to me untrue to our strengths, and bad intellectually, and bad professionally for graduate students.

Exhibit X:

Colleges and universities should welcome intellectual pluralism and the free exchange of ideas. Such a commitment will inevitably encourage debate over complex and difficult issues about which individuals will disagree. Such discussions should be held in an environment characterized by openness, tolerance and civility. [...]

The validity of academic ideas, theories, arguments and views should be measured against the intellectual standards of relevant academic and professional disciplines. Application of these intellectual standards does not mean that all ideas have equal merit. The responsibility to judge the merits of competing academic ideas rests with colleges and universities and is determined by reference to the standards of the academic profession as established by the community of scholars at each institution.

I'm just sayin'.

N can't be 1, so P must be 0.

American Scientist has an article about Sudoku that is both fascinating and infuriating. Fascinating because it describes the convoluted history of Sudoku, or as it is known in Japan, `Number Place'. (Yes, in English.) Infuriating because, despite claiming to be an article about computering science, the author gets the cornerstone result embarassingly wrong:

Computer science has an elaborate hierarchy for classifying problems according to difficulty, and the question of where Sudoku fits into this scheme has elicited some controversy and confusion. It is widely reported that Sudoku belongs in the class NP, a set of notoriously difficult problems; meanwhile, however, many computer programs effortlessly solve any order-3 Sudoku puzzle. There is actually no contradiction in these facts, but there is also not much help in dispelling the confusion.

Complexity classes such as NP do not measure the difficulty of any specific problem instance but rather describe the rate at which difficulty grows as a function of problem size. If we can solve an order-n Sudoku, how much harder will we have to work to solve a puzzle of order n + 1? For problems in NP, the effort needed grows exponentially.

Umm... not quite.

NP stands for `Nondeterministic Polynomial time'. A problem is in the class NP if an afirmative answer can be verified by an algorithm whose running time grows only polynomially as a function of the input size. Yes, Sudoku is in NP—to prove that the puzzle has a solution, just show me the solution—but so is the problem `Are these numbers in sorted order?' Membership in NP is a statement about how easy a problem is, not how hard.

Similarly, a problem is in the class P if it can be solved from scratch in polynomial time.

A (The? No, just a) central open question in theoretical computer science is whether P=NP—is it just as easy to solve problems from scratch as it is to verify their solutions? It is widely (but not quite universally) believed that the answer is no. Most computer scientists believe that some problems in NP require exponential time. Sudoku is one of those problems. But we have no proof (or disproof) that Sudoku requires exponential time, or even a good idea how to approach a proof (or disproof). In fact, we have a proof that we have no idea how to approach a proof (or disproof)!

Sudoku is an example of an NP-hard problem. Intuitively, a problem is NP-hard if a polynomial-time algorithm to solve that problem would imply that P=NP. More formally, problem X is NP-hard if one of two conditions holds:

• X is the Circuit Satisfiability problem: Given a logical circuit with toggle switches at one end and a lightbulb at the other, can you turn on the light?
• There is a polynomial-time many-one reduction from some other NP-hard problem to X.

Yato and Seta proved that order-n Sudoku is NP-hard [pdf] by reduction from Latin Square Completion (which was proved NP-hard by reduction from 1-in-4-SAT (which can be proved NP-hard by reduction from Circuit Satisfiability)). In fact, Yato and Seta prove that if we are given 100 solutions to an order-n Sudoku problem, it is NP-hard to determine whether there is a 101st solution, for arbitrary values of 100.

That is so cool. And the article screwed it up! Argh!

Sorry? What's that, Dave?

So what lesson do I draw for this for the theory of CS? Well they need a Richard Feynman and a Stephen Hawking! But seriously, they need to attempt to convey their results in a way which, while not toally faithful to the science, gives the reader a reason to believe that they understand what is going on. This, of course, is much hard to do as a computer scientist than as a theoretical physicist because in the former rigor is held in higher esteem than in physics where hand-wavy arguments hold a much greater standing. But certainly even theoretical physicists (except the best) have to distort their understandings to meet the general public. So my advice to the theoretical computer science community is to let the rigor go but convey the spirit in a way that convince the public they understand what is going on.

Hmmm. Maybe he's right. Maybe I should be satisfied that American Scientist is using the letters N and P at all. (Grumble.)

[via Marginal Revolution]

Core dump

• Monkey throws crap at flying spaghetti monster. Monkey apologizes. Flying spaghetti monster hits monkey with pipe.

• Papers, please.

• Hmmm... then again, maybe not.

• Go Shorty. It's ya birthday. Gonna party like it's ya birthday.

• The Third Duodecennial Academic Mutual Admiration Society Shark-Feeding, Lottery, Symposium, and/or Pie-Bake-Off

• Fucking graphing calculators!

• How low, how low, how low can you go?

Yippee ya ya, yippee yay!

Neubatuen einstürzen. Es gibt immer was zu tun.

Ph’nglui mglw’nafh Cthulhu R’lyeh wgah’nagl fhtagn!