Skip to main content
2 votes

Are these two definitions related to strong NP-hardness equivalent?

They are not quite equivalent. Note that every NP-hard problem (also in the weak sense) has by definition a polynomial time reduction from all problems in NP, including from those that are strongly NP-...
ttnick's user avatar
  • 1,678

Only top scored, non community-wiki answers of a minimum length are eligible