P = NP?

[LooseCaboose]

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:

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:

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.

[Agamemnus]

Yes, yes and yes, but! NP hard? NP complete? Irrelevant!

The question is:

Is P = NP ?

Which can simply be proved by finding a problem in that has a solution in P and another method for that solution in NP.

Code:

In complexity theory, NP ("Non-deterministic Polynomial-time") is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine.

Code:

In this theory, the class P consists of all those decision problems that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input;

And my problem can be solved both in P and in NP.

And if it is in NP it is NP-hard and NP-complete.

It is NP-hard because it is as least as hard as any problem in NP; itself. And it is NP-complete for the same reason.

This circular logic is getting stupid. I'm going to read the problem description again.

[LooseCaboose]

Which can simply be proved by finding a problem in that has a solution in P and another method for that solution in NP.

You can't solve it like that at all. P and NP are classes of problems. For P to be equal to NP then /all/ problems in NP must also be in P, not /a/ given problem that you show solutions to exist in both classes.

Your argument is like having two sets g and h and claiming that if one element is in both g and h, then it logically follows that all elements that are in g are also in h. This is not true.

NP hard? NP complete? Irrelevant!

These are highly relevant, you claiming that they are not is just showing that you still do not understand the problem.

To attack the P = NP question, the concept of NP-completeness is very useful. Informally, the NP-complete problems are the "toughest" problems in NP in the sense that they are the ones most likely not to be in P. This means that if a single NP-complete problem could be shown to be in P, then it would follow that P = NP. Unfortunately, many important problems have been shown to be NP-complete and not a single fast algorithm for any of them is known.

And my problem can be solved both in P and in NP.

Good for you. Unfortunately any problem that already exists in class P can have a "bad" algorithm constructed for it to place it in class NP. What exactly are you trying to prove?

And if it is in NP it is NP-hard and NP-complete.

Which your problem is not. The travelling salesman problem and the knapsack problem for example are. Can you show me an algorithm for either of these that can place them in the P class?

It is NP-hard because it is as least as hard as any problem in NP; itself. And it is NP-complete for the same reason.

Your problem is neither NP-Hard nor NP-Complete. You are misinterpreting the definitions of both.

This circular logic is getting stupid. I'm going to read the problem description again.

What circular logic? You either can or cannot show that one of the /existing/ NP-Complete problems has a solution in P. You are artfully dodging this issue and trying to create proofs that are irrelevant to the actual problem.

[Agamemnus]

Ok, so let's try a different approach.

1) You say that this algorithm is neither NP-hard nor NP-complete. Why, exactly?

2) You say "Good for you. Unfortunately any problem that already exists in class P can have a "bad" algorithm constructed for it to place it in class NP." So then, explain to me, why the solutions to other NP problems that you mentioned are not "bad" algorithms, but "good" algorithms.

Since you're trying to find some polynomial algorithm for this exponential a^n algorithm, then when you do so, your old algorithm is now considered "bad" and your new algorithm OK, and you now render the problem itself as irrelevant in the question "P=NP?"