What good books are there on the subject of P = NP, NP-completeness and the like?
I have Fortnow's "The Golden Ticket" and Garey & Johnson's "Computers and Intractability"
How else can I get into the subject and slowly creep towards the forefront of research? Who is actively researching it? What literature/publications can I read to bring me up to speed?
Other urls found in this thread:
scottaaronson.com
youtube.com
twitter.com
bump for interest
scottaaronson.com
116 page survey of the state of the art that was recently published.
Thank me later.
Wow, this looks pretty good. Thank you user.
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.
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
OP is a fast reader.
>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?
But why?
>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.
Thank you user.
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?
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 ?
>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).
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?
are you literally retarded or something ?
i was hoping for some user 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?
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.
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.
The Bible.
Thanks! Great read!
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.
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.
