[ipnon]

Jim Gray's New York Times obituary https://bits.blogs.nytimes.com/2008/05/31/a-tribute-to-jim-g...

[briefcomment → ipnon]

Looked him up and came across the fact that he evaluated the Club of Rome's overpopulation model and concluded it was wrong [1], and that he eventually (decades later) disappeared at sea. Almost certainly unrelated, but it's hard to escape conspiratorial thinking these days.

[smiljo]

Easy one for me: Stephen A. Cook. Proved that SAT was NP-complete and formulated the P vs. NP problem.

IMO, even among Turing Award winners there are tiers, and he's in the top one in my book.

[yesenadam → smiljo]

I had to google "SAT":

"In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE... For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable.

SAT is the first problem that was proven to be NP-complete... This means that all problems in the complexity class NP, which includes a wide range of natural decision and optimization problems, are at most as difficult to solve as SAT. There is no known algorithm that efficiently solves each SAT problem, and it is generally believed that no such algorithm exists; yet this belief has not been proven mathematically, and resolving the question of whether SAT has a polynomial-time algorithm is equivalent to the P versus NP problem..."

https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

https://en.wikipedia.org/wiki/Stephen_Cook

[jjice → yesenadam]

The NP encapsulation diagram is so interesting. From someone who took a few theory classes, but not a ton, it's very interesting and mystifying. One day, I hope there can be some sort of proof for P vs NP, one way or the other. Mostly because it's a problem that is relatively understandable, but crazy to think we don't have an answer. The idea that P=NP would be an incredible proof to see (or watch someone dissect) because (from what I remember from my algo class) that means that all NP problems can be traced to some root problem that can be used to solve it. That root problem would be an incredible thing to see.

If it wasn't obvious, I'm not very knowledgeable on this topic.

[ipnon → smiljo]

It's a succinct paper. http://4mhz.de/download.php?file=Cook1971_Letter.pdf