NP vs NP-complete vs NP-hard

Правка en2, от balsa_knez, 2020-08-12 01:41:44

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! :)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский balsa_knez 2020-08-12 01:41:44 0 (published)
en1 Английский balsa_knez 2020-08-12 01:40:21 1564 Initial revision (saved to drafts)