What good books are there on the subject of P = NP, NP-completeness

>>58735886
bump for interest

>>58735886
http://www.scottaaronson.com/papers/pnp.pdf
116 page survey of the state of the art that was recently published.

Thank me later.

>>58736033
Wow, this looks pretty good. Thank you anon.

>>58736143
HE SAID LATER

I've been a profesional software engineer for 16 years and still don't know that P = NP is all about.

Is okay though, an computer assemblyman doesn't have to know how the components he's assembling work.

>>58736570
It's a CS problem, not an engineering problem. Shit is mostly a concern for mathematicians anyways, but the repercussions of a proof are, as always, in the mechanism we'd find to get here and how powerful that math could be to other uses.

The Nature of Computation
Moore

>>58736152

OP is a fast reader.


>>58736570

>I've been a profesional software engineer for 16 years and still don't know that P = NP is all about.

Try to make an algorithm that finds the shortest tour among a few cities (without visiting a city twice). No matter how good you are it will take kinda long.

No try to sort an array:
Wow, that was much faster, wasn't it?

>>58737348
But why?

>>58736570
>I've been a profesional software engineer for 16 years and still don't know that P = NP is all about.
>professional
yeah, nope. pajeet level at best.

>>58736033
Thank you anon.

what exactly is P and NP? i understand they are sets of problem types but can someone explain what it means to solve a problem "in polynomial time"? or what a question and answer may look like?

>>58738984
they are complexity classes.

>but can someone explain what it means to solve a problem "in polynomial time"?
you don't know what polynomial means ? did you ever attend a school ?

>>58738984
>what it means to solve a problem "in polynomial time"?
In a number of operations that has polynomial complexity (i.e.: that converges to a polynomial function when the size of the input grows).

>>58739023
i know what polynomial functions look like, but i mean what is the metric? does time translate to literal seconds or is it processor cycles or math operations or what?

>>58739051
are you literally retarded or something ?

>>58739077
i was hoping for some anon who was smarter than me to break it down and make teach me something.

i'm ignorant on the subject. do you feel better now?

>>58739051
Usually it's count of a certain operation, and even more usually comparision.

We're talking algorithms here so an entire instruction set model doesn't make much sense.

>>58739125
no, but i feel sorry for you. are you american ?

anyway, you said you know what a polynomial function looks like. just imagine that thats how the runtime grows with the size of the input set.
now look up an exponential function e.g.

>>58735886
The Bible.

>>58736033
Thanks! Great read!

>>58739125
Say you want to search an array for an element.
Best case scenario is it's the first element in the array. Happy dayz
Worst case scenario is the element isn't even in the array. Thus you've made N comparisons where N is the number of elements in the array, and haven't found the thing you were looking for.
So the average case is N/2.

>>58739125
Now suppose you want to see if any element from one array is present in another. If the first array has M elements and the second array has N elements, then the worst case scenario will be M * N comparisons. See how this differs from the first algorithm? The running time increases depending on the algorithm.
Now you have an idea of what time complexity is.

>>58739125
https://www.youtube.com/watch?v=YX40hbAHx3s