CODEWITHSUNDEEP
graph-theorynpnp-hardcomputability
user7821248
user7821248

Reputation:

Make the assumption that P = NP

Suppose P = NP, would that mean that Hamiltonian-Cycle is no longer NP-Hard? Hamiltonian-Cycle is a language where a given graph G contains a Ham-Cycle.

Upvotes: 2

Views: 82

Answers (1)

tbrugere
tbrugere

Reputation: 1623

The definition of NP-Hard is that it allows you to solve a NP-complete problem, which is a fancy way of saying "solving this problem is at least as hard as solving any NP problem".

If P = NP, a NP-hard problem stays NP-hard, in the sense that "solving this problem is still at least as hard as solving any NP problem". But since P = NP, this is equivalent to "solving this problem is at least as hard as solving any P problem". Which is generally not considered hard

Upvotes: 1

Related Questions