I recommend Computational Complexity: A Modern Approach readable, and covers all the topics
link to the free draft
Introduction to P vs. NP
21–30 of 41 posts
Re: Introduction to P vs. NP
#22I like GPT-4's explanation of P vs NP. Prompt: "Give me good computer science arguments for why P = NP and why P != NP" Response: "The P vs. NP problem is a major open question in computer science, which asks whether problems whose solutions can be quickly verified by a computer can also be quickly solved by a computer. Both sides of the argument have been extensively debated, but the problem remains unsolved. Here a…
It's kind of disappointing that GPT-4 defines NP-completeness in terms of Turing/Cook reductions while Karp reductions have been the preferred definition for the last half century or so. For example, under GPT-4's definition there is no distinction between NP-Completeness and Co-NP-Completeness. I guess that speaks to the volumes of laymen explanations out there.
What in the response indicates Turing or Cook reductions? I would say the answer does not go into nearly enough technical details to conclude anything like that, it does not even mention [polynomial time] reductions. Even among the people seeking some understanding of the P vs NP problem this is a level of technical detail essentially relevant to almost none of them. I studied computer science and if we ever discussed the distinction between different kinds of polynomial time reductions, then this got erased from my memory long ago. And if you really need this level of technical detail, then you can probably ask for it.
Re: Introduction to P vs. NP
#23For the laymans out there: pls don't just randomly use words like NP-complete or NP-hard or such, when you only know that a problem is "hard", or you don't see a trivial solution. It's exponentially annoying.
Re: Introduction to P vs. NP
#24I wonder who needs to know this who doesn’t also need to know the difference between a decision (yes/no) problem and a general problem. This is relevant because P and NP are only defined for decision problems, but all of the examples given aren’t such problems.
Re: Introduction to P vs. NP
#25I wonder who needs to know this who doesn’t also need to know the difference between a decision (yes/no) problem and a general problem. This is relevant because P and NP are only defined for decision problems, but all of the examples given aren’t such problems.
Can't general problems be reduced to decision problems though?
Re: Introduction to P vs. NP
#26One problem here ... it needs to come with a huge caveat: this is much more a theoretical discussion than necessarily a practical one. This is to say, it's possible for a problem the best P algorithm we can find takes n^(10^82) time while the NP algorithm we can find is say (1.00000000.....(10^82 zeroes)... 1)^n. For any practical number the NP algorithm will be faster. (I used 10^82 because it's the approximate numb…
Yes, I agree. Complexity theory is probably one of the least practical fields for software _engineers_, it can even work to a detriment, because you can discouraged to find solutions to problems.
On the other hand, I have had great benefit from studying PL and semantics for software engineering. It taught me to write more readable and reliable code.
(From a person who studied both as a part of his master)
Re: Introduction to P vs. NP
#27I wonder who needs to know this who doesn’t also need to know the difference between a decision (yes/no) problem and a general problem. This is relevant because P and NP are only defined for decision problems, but all of the examples given aren’t such problems.
Can't general problems be reduced to decision problems though?
All I've seen pretty much can.
Each solution can be encoded as an integer, and as long as you can construct your query as "is solution less than N?", you can use binary search to solve the problem in log(n) repetitions of the query, which does not affect the complexity class.
Re: Introduction to P vs. NP
#28Earlier quoted context omitted.
Can't general problems be reduced to decision problems though?
All I've seen pretty much can. Each solution can be encoded as an integer, and as long as you can construct your query as "is solution less than N?", you can use binary search to solve the problem in log(n) repetitions of the query, which does not affect the complexity class.
I am a bit rusty on this theory but isn't the N in your case related to the output size while you would need it to be related to input size instead?
Re: Introduction to P vs. NP
#29Earlier quoted context omitted.
You don't need to involve a P vs NP discussion at all if you want to have a practical discussion to begin with. Big-Oh is sufficient?
Profiling the code with different size inputs is sufficient
I don’t know, I think knowing what algorithmic complexity is is really important, the problem is that all too many people just memorized that bubble sort is O(n^2) without understanding.
Also, the reason why profiling is imo not good enough is that you really shouldn’t even try to write an implementation with a known-to-be “slow” algorithm at the designed input size. For that, understanding O-notation is essential.
Re: Introduction to P vs. NP
#30[deleted]