Search code examples
graphcomplexity-theorygraph-theorynp-completenp

NP complete or NP hard, in a equivalences problems?

I ran into a question.

Finding of all cycle in a graph is NP-Complete.

I see this note on Google search.

counting all cycle in a graph is NP-Complete.

are these two sentence equivalences ? can we say these two is NP-Hard?

Thanks for every useful note.

Solution

  • are these two sentence equivalences ?

    Yes but it's not phrased properly. None of those questions are decision problems. Decision problems return either true or false. NP-Complete is a categorization of decision problems so it'll be "improper" to say the above are NP-Complete. But if we say, "Are there X number of cycles in a graph?" that would be a NP-Complete question.

    can we say these two is NP-Hard? Yes NP-Hard means it's as hard as NP at least so because these two problems are NP-Complete then this is true.