31–37 of 37 posts
Earlier quoted context omitted.
A problem harder than NP would not even be verifiable in polynomial time, which I believe would limit their practicality.
If it was verifiable in NP time, and P = NP, then wouldn't it also be verifiable in polynomial time?
It could mean that certain problems which are known to be "difficult" (cryptography, factoring multiples of primes, traveling salesman, bin-packing, etc.) may not be inherently "difficult" and may have solutions (yet to be found) which can solve the problem in polynomial time. There are many things built on top of the fact that certain types of problems are not easily solvable - cryptography being the most obvious -…
That's not entirely accurate. There are many problems that are untractable (i.e. can't solve them because of the nature of the problem) but have nothing to do with P=NP. Consider the halting problem, for instance.
Earlier quoted context omitted.
You are right, I confused NP with NP-hard. However, I think it's safe to assume that if a polynomial solution exists for a NP-hard problem, the complexity wouldn't be so incredibly high than it's better to use heuristics.
> I think it's safe to assume that if a polynomial solution exists for a NP-hard problem, the complexity wouldn't be so incredibly high than it's better to use heuristics. How is this possibly safe to assume? The “heuristic” methods aim for a “good enough” solution rather than “the best solution”. Whyever would a polynomial time algorithm for exactly solving an NP-hard problem be faster than polynomial time “heuristi…
Earlier quoted context omitted.
A problem harder than NP would not even be verifiable in polynomial time, which I believe would limit their practicality.
If it was verifiable in NP time, and P = NP, then wouldn't it also be verifiable in polynomial time?
It could mean that certain problems which are known to be "difficult" (cryptography, factoring multiples of primes, traveling salesman, bin-packing, etc.) may not be inherently "difficult" and may have solutions (yet to be found) which can solve the problem in polynomial time. There are many things built on top of the fact that certain types of problems are not easily solvable - cryptography being the most obvious -…
It could mean that certain problems which are known to be "difficult" (cryptography, factoring multiples of primes, traveling salesman, bin-packing, etc.) may not be inherently "difficult" and may have solutions (yet to be found) which can solve the problem in polynomial time. There are many things built on top of the fact that certain types of problems are not easily solvable - cryptography being the most obvious -…
> The way I like to think about NP is: are there certain types of problems which we, as smart as we might be, cannot easily solve, not because we aren't smart enough but because of the nature of the problem itself? That's not entirely accurate. There are many problems that are untractable (i.e. can't solve them because of the nature of the problem) but have nothing to do with P=NP. Consider the halting problem, for i…
Can you elaborate some more on this? I'd like to learn more about this area. Are you referring to problems for which no polynomial time solution exists, and there is also no polynomial time method for verifying a solution?
Earlier quoted context omitted.
> The way I like to think about NP is: are there certain types of problems which we, as smart as we might be, cannot easily solve, not because we aren't smart enough but because of the nature of the problem itself? That's not entirely accurate. There are many problems that are untractable (i.e. can't solve them because of the nature of the problem) but have nothing to do with P=NP. Consider the halting problem, for i…
There are many problems that are untractable (i.e. can't solve them because of the nature of the problem) but have nothing to do with P=NP Can you elaborate some more on this? I'd like to learn more about this area. Are you referring to problems for which no polynomial time solution exists, and there is also no polynomial time method for verifying a solution?
> The way I like to think about NP is: are there certain types of problems which we, as smart as we might be, cannot easily solve, not because we aren't smart enough but because of the nature of the problem itself?
If you read it one way, it sounds as if P=NP would allow us to solve every formal problem. It doesn't. One very interesting example:
The concept of Kolmogorov Complexity. I'm not a CS theorist, so I can only give my layman interpretation, but if I understand it well it goes like this: given a particular string of bits, the Kolmogorov Complexity relates to the shortest possible program that can describe this string. In effect, that means: the ultimate compression. Well, the whole theory of KC says that you can't find this shortest possible program for every string. Not because it takes too much time to check very possible combination (P=?=NP) but because of the nature of the problem.