7
$\begingroup$

If one were to learn more about the $P \stackrel{?}{=} NP$ problem, where would one start?

I understand what the problem is—but not enough to be able to read anything technical about it. Furthermore, I don't know where to start. When reading "This problem can be solved in $n^k$ steps" I only have a vague clue about how one goes about rigorously proving a statement like that.

Would getting an introductory book in something like boolean algebra be of use? Or should one focus more directly on computational complexity?

$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

You should get a book on theoretical computer science, which will cover at least formal languages/automata, computability, and complexity. Sipser's "Introduction to the Theory of Computation" is widely used and a good place to start. From there you can start picking up auxiliary resources depending on what you have a hard time understanding.

A MOOC course might also be helpful. Here's UDacity's Intro to Theoretical Computer Science

$\endgroup$
2
$\begingroup$

Here is a classical book: Hopcroft J.and others Introduction to Automata Theory, Languages, and Computation. You can star from the chapter about Turing machines and go further. And here there is a video-lectures on the topic.

$\endgroup$
2
$\begingroup$

There are several books on Computational Complexity; I like the one by Papadimitriou.

The subject belongs more to Theoretical Computer Science than Mathematics, so you may find useful to ask at cstheory.stackexchange.com or take a look at book recommendations for corresponding computer science classes in various universities: many of the have class requirements in online schedules.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .