tags: ,

More computer scientists are elected to the academy

Dan Mote, the President of the National Academy of Engineering (NAE), just announced this year’s class of members elected to the NAE.

Today, I am thrilled to see that several computer scientists were among the class.

Actually in putting together the list below of computer science members I had some difficulty. If I made an error I apologize in advance. One of the interesting results of looking at the whole list of 80 members is that computing played a major role in many member’s citations. Yet for many of these I would not classify them as computer scientists. This is just another example of the importance of computing in all of engineering. So if I left out someone from what I considered another area, well I am sorry.

Congratulations to all on your election.

## The New Members

Here are the new members, along with their citations. The NAE likes pithy citations that start with the word “For.”

• Anderson, Thomas, University of Washington, Seattle. For contributions to the design of resilient and efficient distributed computer systems.

• Boneh, Dan, Stanford University, Stanford, Calif. For contributions to the theory and practice of cryptography and computer security.
• Chang, Frederick, Southern Methodist University, Dallas. For leadership in cybersecurity research in the intelligence community and advancing the importance of cybersecurity science in academia.
• Cornuéjols, Gérard, Carnegie Mellon University, Pittsburgh. For contributions to the theory, practice, and application of integer programming.
• Greenberg, Albert, Microsoft Corp., Redmond, Wash. For contributions to the theory and practice of operating large carrier and data center networks.
• Hinton, Geoffrey, Google Inc., Toronto (foreign member). For contributions to the theory and practice of artificial neural networks and their application to speech recognition and computer vision.
• Jain, Anil, Michigan State University, East Lansing. For contributions to the engineering and practice of biometrics.
• Johnson, David, Columbia University, New York City. For contributions to the theory and practice of optimization and approximation algorithms.
• Leiserson, Charles, Massachusetts Institute of Technology, Cambridge. For theoretically grounded approaches to digital design and parallel computer systems.
• Lindsay, Bruce, IBM Almaden Research Center, San Jose, Calif. For the design and implementation of high-performance distributed and extensible database systems.

I cannot resist to say that I have a personal connection to both Boneh and Leiserson. I was honored to be the graduate advisor of Dan and the undergraduate advisor to Charles: the former at Princeton and the latter at Yale. Both were a delight to work with, and I am very excited that they are now in the academy.

I also noticed that areas that were selected for recognition were concentrated into three. Security was covered several times; large scale systems of several kinds was also; and theory was key for two new members.

Ken points out that all ten precede me in the alphabet—indeed they run snugly up to “Lip—.” As a member I voted but had no effect there.

## Open Problems

The main issue that confronts computer science is to get more members into the NAE. Many deserving researchers are not yet members and I hope that will be solved in the future. But for today let’s congratulate all those who did get into the NAE this year.

Ken: We are leaving yesterday’s post “unrolled” on the front page since this comes so soon after. To keep it short we elided material on deep learning and big data including this interview that would have brought “engineering” into the “science” versus “magic” issue.

One Comment leave one →
1. February 9, 2016 2:12 pm

Dear Professor,

Is $$P$$ equal to $$NP$$?

We pretend to show the answer of the $$P$$ versus $$NP$$ problem. Our principal argument is based in a technique that has been used throughout history in both formal mathematical and philosophical reasoning, as well as informal debate: The Reductio ad absurdum. Reductio ad absurdum is a common form of argument which seeks to demonstrate that a statement is true by showing that a false, untenable, or absurd result follows from its denial, or in turn to demonstrate that a statement is false by showing that a false, untenable, or absurd result follows from its acceptance.

We start assuming the hypothesis of $$P = NP$$ that will lead us to a contradiction. The argument is supported by a Theorem that states if $$P = NP$$, then the problem SUCCINCT HAMILTON PATH would be in $$P$$. In this Theorem, we take an arbitrary succinct representation $$C$$ of a graph $$G_{C}$$ with $$n$$ nodes, where $$n = 2^{b}$$ is a power of two and $$C$$ will be a Boolean circuit of $$2 \times b$$ input gates. Interestingly, if $$C$$ is a “yes” instance of SUCCINCT HAMILTON PATH, then there will be a linear order $$Q$$ on the nodes of $$G_{C}$$, that is, a binary relationship isomorphic to “<" on the nodes of $$G_{C}$$, such that consecutive nodes are connected in $$G_{C}$$. This linear order $$Q$$ must require several things:

* All distinct nodes of $$G_{C}$$ are comparable by $$Q$$,
* next, $$Q$$ must be transitive but not reflexive,
* and finally, any two consecutive nodes in $$Q$$ must be adjacent in $$G_{C}$$.

Any binary relationship $$Q$$ that has these properties must be a linear order, any two consecutive elements of which are adjacent in $$G_{C}$$, that is, it must be a Hamilton path.

On the other hand, the linear order $$Q$$ can be actually represented as a graph $$G_{Q}$$. In this way, the succinct representation $$C_{Q}$$ of the graph $$G_{Q}$$ will represent the linear order $$Q$$ too. We can define a polynomially balanced relation $$R_{Q}$$, where for all succinct representation $$C$$ of a graph: There is another Boolean circuit $$C_{Q}$$ that will represent a linear order $$Q$$ on the nodes of $$G_{C}$$ such that $$(C, C_{Q})$$ is in $$R_{Q}$$ if and only if $$C$$ is in SUCCINCT HAMILTON PATH.

It is easy to see, the graphs $$G_{C}$$ and $$G_{Q}$$ will comply with $$|G_{Q}| < |G_{C}|^{3}$$ when $$(C, C_{Q})$$ is in $$R_{Q}$$, since both graphs would have the same number of nodes and $$G_{C}$$ would contain a Hamilton path. Consequently, we obtain the same property for their succinct representations, that is, $$C_{Q}$$ should be polynomially bounded by $$C$$. Indeed, for a sufficiently large $$n$$, the Boolean circuits $$C$$ and $$C_{Q}$$ will be exponentially more succinct than $$G_{C}$$ and $$G_{Q}$$ respectively. Hence, if the graph $$G_{Q}$$ is polynomially bounded by the graph $$G_{C}$$ when $$(C, C_{Q})$$ is in $$R_{Q}$$, then $$\log_{2} |G_{Q}|$$ will be polynomially bounded by $$\log_{2} |G_{C}|$$.

We finally show $$R_{Q}$$ would be polynomially decidable if $$P = NP$$. For this purpose, we use the existential second-order logic expressions, used to express this graph-theoretic property (the existence of a Hamilton path), that are described in Computational Complexity book of Papadimitriou: Chapter "5.7 SECOND-ORDER LOGIC" in Example "5.12" from page "115". Indeed, we just simply replace those expressions with Universal quantifiers into equivalent Boolean tautologies.

Certainly, a language $$L$$ is in class $$NP$$ if there is a polynomially decidable and polynomially balanced relation $$R$$ such that $$L = \{x: (x, y) in R for some y\}$$. In this way, we show that SUCCINCT HAMILTON PATH would be in $$NP$$ if we assume our hypothesis, because the relation $$R_{Q}$$ would be polynomially decidable and polynomially balanced when $$P = NP$$. Moreover, since $$P$$ would be equal to $$NP$$, we obtain that SUCCINCT HAMILTON PATH would be in $$P$$ too.

But, we already know if $$P = NP$$, then $$EXP = NEXP$$. Since SUCCINCT HAMILTON PATH is in NEXP–complete, then it would be in EXP–complete, because the completeness of both classes uses the polynomial-time reduction. But, if some EXP–complete problem is in $$P$$, then $$P$$ should be equal to $$EXP$$, because $$P$$ and $$EXP$$ are closed under reductions and $$P$$ is a subset of $$EXP$$. However, as result of the Hierarchy Theorem the class $$P$$ cannot be equal to $$EXP$$. To sum up, we obtain a contradiction under the assumption that $$P = NP$$, and thus, we can claim that $$P$$ is not equal to $$NP$$ as a direct consequence of applying the Reductio ad absurdum rule.

You could see the details in:

https://hal.archives-ouvertes.fr/hal-01270398/document

Regards,
Frank.