# Is the P vs. NP question part of mathematics? **URL:** \ **Category:** Great Debates\ **Created:** [November 24, 2001, 8:17pm UTC](https://boards.straightdope.com/t/is-the-p-vs-np-question-part-of-mathematics/95056 "2001-11-24T20:17:28Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 24, 2001, 8:17pm UTC](https://boards.straightdope.com/t/is-the-p-vs-np-question-part-of-mathematics/95056/1 "2001-11-24T20:17:28Z")
Over in [this](http://boards.straightdope.com/sdmb/showthread.php?threadid=100655) thread, **ftg** makes the following assertion: > [@](#): > > As an old time CS hand, I am constantly surprised to see “P=NP?” pop up on such lists. It is a major open question in Computer Science and not Mathematics. It is as jarring as if you saw questions about room-temperature superconductors or life on mars on a Math list. It just doesn’t belong. To put it plainly, I disagree. The question at hand is that of the equality of two sets; if that’s not a mathematical question, then what is it? More generally, I’d like to argue that some subdisciplines of computer science are also subdisciplines of mathematics. Barring the possibility that my professors have been lying to me, the crux of theoretical computer science is Turing computability. In particular, the sets P and NP are defined in terms of Turing machine computations. From this, it seems sufficient to argue that the theory of Turing machines is mathematical in nature. A Turing machine can be defined as an ordered 7-tuple of sets that satisfy a few axioms. Referring to the standard definitions of set theory (in particular, that of an ordered n-tuple), we have that a Turing machine is a set. The theory of sets is definitely mathematical; therefore, Turing computability is a mathematical theory. Therefore, some subdiscipline of computer science is also a subdiscipline of mathematics. Clearly, neither discipline is a subdiscipline of the other; however, I think I’ve argued that they do have a non-empty intersection. I apologize for my inability to find links on the subjects at hand for those who are not familiar with this material. I use books for my information; in particular, I was looking at [this](http://www.amazon.com/exec/obidos/ASIN/053494728X/qid=1006632777/sr=8-1/ref=sr_8_3_1/102-8192466-8376969) book and [this](http://www.amazon.com/exec/obidos/ASIN/0412808307/qid=1006632843/sr=8-1/ref=sr_8_3_1/102-8192466-8376969) book. ---
**Author:** ![Revtim](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/revtim/32/1042_2.png) [@Revtim](https://boards.straightdope.com/u/Revtim)\ **Post date:** [November 24, 2001, 8:24pm UTC](https://boards.straightdope.com/t/is-the-p-vs-np-question-part-of-mathematics/95056/2 "2001-11-24T20:24:57Z")
I always considered the entirety of Computer Science a subset of Mathematics. Nothing in my college years getting a degree in CS or my subsequent 12+ years in software development has changed my mind. Not I think about it too much, though. Maybe a counter-example would change my mind. ---
**Author:** ![tracer](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tracer/32/20578_2.png) [@tracer](https://boards.straightdope.com/u/tracer)\ **Post date:** [November 24, 2001, 8:30pm UTC](https://boards.straightdope.com/t/is-the-p-vs-np-question-part-of-mathematics/95056/3 "2001-11-24T20:30:10Z")
Personally, I think the “P =? NP” problem should be part of mathematics, because math geeks tend to be **much** better at doing proofs than computer geeks. Therefore, putting “P =? NP” into the field of mathematics will mean that the problem will be solved **much** sooner than if we left it in the hands of a bunch of C++ programmers. And the sooner we either (A) get a proof that NP-complete problems cannot be solved in P time, or (B) come up with a way to turn an NP-complete problem into a P problem, then the sooner we will either be able to sleep better at night (in the case of (A)), or be forced to come up with an encryption scheme whose code-cracking solution lies entirely outside NP (in the case of (B)). Either of these outcomes will be preferable to this no-man’s-land of ignorance we’re wallowing in today! ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 24, 2001, 9:41pm UTC](https://boards.straightdope.com/t/is-the-p-vs-np-question-part-of-mathematics/95056/4 "2001-11-24T21:41:48Z")
> [@](#): > > \*Originally posted by Revtim \* > \*\*I always considered the entirety of Computer Science a subset of Mathematics. Nothing in my college years getting a degree in CS or my subsequent 12+ years in software development has changed my mind. > > Not I think about it too much, though. Maybe a counter-example would change my mind. \*\* I had in mind the studies of architecture and documentation when I said that not all computer science is math. ---
**Author:** ![Spiritus\_Mundi](https://avatars.discourse-cdn.com/v4/letter/s/c68b51/32.png) [@Spiritus\_Mundi](https://boards.straightdope.com/u/Spiritus_Mundi)\ **Post date:** [November 25, 2001, 1:48am UTC](https://boards.straightdope.com/t/is-the-p-vs-np-question-part-of-mathematics/95056/5 "2001-11-25T01:48:33Z")
but questions of set correspondence are. ---
**Author:** ![JubilationTCornpone](https://avatars.discourse-cdn.com/v4/letter/j/ee59a6/32.png) [@JubilationTCornpone](https://boards.straightdope.com/u/JubilationTCornpone)\ **Post date:** [November 25, 2001, 1:57am UTC](https://boards.straightdope.com/t/is-the-p-vs-np-question-part-of-mathematics/95056/6 "2001-11-25T01:57:28Z")
> [@](#): > > \*Originally posted by ultrafilter \* > \*\* > > > [@](#): > > > > \*Originally posted by Revtim \* > > \*\*I always considered the entirety of Computer Science a subset of Mathematics. Nothing in my college years getting a degree in CS or my subsequent 12+ years in software development has changed my mind. > > > > Not I think about it too much, though. Maybe a counter-example would change my mind. \*\* > > I had in mind the studies of architecture and documentation when I said that not all computer science is math. \*\* In addition, questions of programming style have little to do with mathematics. If anything, they are linguistic in nature. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 25, 2001, 4:02am UTC](https://boards.straightdope.com/t/is-the-p-vs-np-question-part-of-mathematics/95056/7 "2001-11-25T04:02:03Z")
> [@](#): > > \*Originally posted by JubilationTCornpone \* > \*\*In addition, questions of programming style have little to do with mathematics. If anything, they are linguistic in nature. \*\* Has there been any formal study of this? I know that getting people to write readable code is extremely important, but AFAIK we’re just guessing on how to do that (and even on what makes a million-line program readable).