Hello,

As I am doing my graduate project and I choose to do the clique problem, I have a few questions about NP-hardness. I have read this post, but I didn't find answers on my questions.

First question: Suppose we can find a problem X that hasn't a polynomial solution and which is not a decision problem. We have to put this problem to the NP-hard set. But if we also cannot find any NP-complete problem Y, such that Y is reducible to our problem X in polynomial time, then X shouldn't belong to NP-hard set. Where shall we put this problem X? Or such a problem cannot be found?

Second question: It's known that problems like the longest path and maximum clique in a graph are NP-hard and they do not have verifier in polynomial complexity. Their decision problems are NP-complete (path of length k, or clique of length k). But, we can easily transform one to another — for example, find maximum clique with checking values for k = 1 up to n and take maximum with the existing clique. So why those problems are not np-complete too? Is the only reason because they are not decision problems? Also why we need a polynomial verifier for maximum clique problem, as we can solve it with calling clique of length k, n times and we can verify that problem in polynomial time? So we know that answer is correct, otherwise, our polynomial verifier for a clique of length k is not correct.

Thanks in advance! :)