1

I guess that every np-complete problem reduces to the np-hard problem, so the given statement is true. But don't know how to prove it.

Matt Timmermans
61k3 gold badges58 silver badges107 bronze badges
asked Jul 29, 2020 at 18:42
2
  • 1
    Halting problem is not NP-hard. It is unsolvable. Commented Jul 29, 2020 at 18:53
  • Every problem in NP reduces to every NP-hard problem, and a problem is NP-complete if it's in NP and it's NP-hard. You don't prove those things. Those are the definitions of NP-complete and NP-hard. You could reduce every NP-complete problem to halting, but why? Commented Jul 29, 2020 at 19:51

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.