My favourite results are (1) the existence of NP-complete problems (Cook), (2) the Baker-Gil-Solovay theorem that whether P=NP holds relativized to on oracle depends on the oracle, and (3) Faggin's characterization of NP in terms of second order logic.

I am not so much interested in the large number of proofs that show that a certain problem is NP-complete, but the fact that there is some problem that is NP-complete is remarkable and important. And Cook's SAT is actually natural. (2) shows that several approaches will not work when one wants to settle P versus NP. (3) gives a much more natural definition of the class NP. Faggin's formulation (NP is the class of graph properties (of finite graphs) that can be expressed with a formula that has an n-ary second order existential quantifier in front, followed by a first order formula) indicates that NP vs co-NP is a very fundamental question as well (can second order existential quantification be replaced by second order universal quantification?).

My favourite results are (1) the existence of NP-complete problems (Cook), (2) the Baker-Gil-Solovay theorem that whether P=NP holds relativized to on oracle depends on the oracle, and (3) Fagin's characterization of NP in terms of second order logic.

I am not so much interested in the large number of proofs that show that a certain problem is NP-complete, but the fact that there is some problem that is NP-complete is remarkable and important. And Cook's SAT is actually natural. (2) shows that several approaches will not work when one wants to settle P versus NP. (3) gives a much more natural definition of the class NP. Fagin's formulation (NP is the class of graph properties (of finite graphs) that can be expressed with a formula that has an n-ary second order existential quantifier in front, followed by a first order formula) indicates that NP vs co-NP is a very fundamental question as well (can second order existential quantification be replaced by second order universal quantification?).

My favourite results are the existence of NP-complete problems (Cook), the Baker-Gil-Solovay theorem that whether P=NP holds relativized to on oracle depends on the oracle, and Faggin's characterization of NP in terms of second order logic.

My favourite results are (1) the existence of NP-complete problems (Cook), (2) the Baker-Gil-Solovay theorem that whether P=NP holds relativized to on oracle depends on the oracle, and (3) Faggin's characterization of NP in terms of second order logic.

I am not so much interested in the large number of proofs that show that a certain problem is NP-complete, but the fact that there is some problem that is NP-complete is remarkable and important. And Cook's SAT is actually natural. (2) shows that several approaches will not work when one wants to settle P versus NP. (3) gives a much more natural definition of the class NP. Faggin's formulation (NP is the class of graph properties (of finite graphs) that can be expressed with a formula that has an n-ary second order existential quantifier in front, followed by a first order formula) indicates that NP vs co-NP is a very fundamental question as well (can second order existential quantification be replaced by second order universal quantification?).