10-17-2003, 05:43 AM
Quote:You are subjectively defining what a hard or easy problem is.
No, computer science is defining what hard and easy problems are. NP-Hard and NP-Complete are types of problems in the NP class: From the Wikipedia:
Quote: the NP-complete problems are the hardest problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use that algorithm to solve all NP problems quickly.
....
NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing the decision problems that are at least as hard as any problem in NP.
....
It is also often used to define the complexity class NP-complete which is the intersection of NP and NP-hard. Consequently the class NP-hard can be understood as the class of problems that are NP-complete or harder.
However, this is what bothers me:
Quote:I read the problem description in the Clay Mathmatics Institute website, but I couldn't make much sense out of it. Neither can I make sense of this:So, you admit that you don't really understand the problem, however you still feel quite comfortable arguing about it and attempting to solve it. I have explained the problem to you, I have explained why it is difficult to solve, I have explained why your solutions do not work and even pointed you in the direction of a possible solution (although mighty difficult, seeing as some of the worlds greatest mathmaticians already know this and haven't figured it out) and still you are either unable or unwilling to listen.
Questions:
How many of the NP-Complete problems have you actually looked at before attempting to solve this?
How well do you understand algorthm complexity, measuring orders and ammortized times of algorithms?
How well do you understand heuristic approaches to some of the NP-Complete problems? The travelling salesman problem, for example can be solved for a "good enough" answer by hand in a relatively short time for around 16-20 cities.
Do you understand Turing thesis and the halting problem and its associated proofs?
Do you understand the difference between countable and uncountable infinity?
Do you know how to construct a proof for an algorithm to show that it works in all cases, hint using mathmatical induction?
These are some of the basics of complexity theory in computer science, if you don't understand any of these completely, you are probably going to get nowhere in your attempts to solve the greatest mystery of theoritical computer science.
esus saves.... Passes to Moses, shoots, he scores!