Stack Exchange Network
Stack Exchange network consists of 181 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Visit Stack Exchange
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Anybody can ask a question
The best answers are voted up and rise to the top
To show that problem is NP-hard, we take a known NP-hard problem and reduce it to the problem whose NP-hardness we want to prove.
The reduction we need is polynomial time reduction.
But If I take known NP-hard problem and reduce it to some unknown problem by Turing reduction then what I can say about the unknown problem?
I am sure that I can't say it is NP-hard, as the reduction is Turing.
273k2626 gold badges301301 silver badges492492 bronze badges
asked Feb 10, 2019 at 15:23