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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.