Skip to main content
Computer Science

Return to Answer

edited body
Source Link
3cnf
3cnf
  • 183
  • 1
  • 9

If one has access to a polynomial algorithm solving $Z$$X$, then there exists a polynomial algorithm for $Z$. That's the main point of reductions for complexity classes. Problem $X$ is at least as hard as problem $Z$.

Another point to be made here is that the class $NP$ is about worst-case complexity, i.e. language $X$ can be $NP$-hard because some instances of $X$ are hard, even if they don't have any corresponding instances in $Z$.

If one has access to a polynomial algorithm solving $Z$, then there exists a polynomial algorithm for $Z$. That's the main point of reductions for complexity classes. Problem $X$ is at least as hard as problem $Z$.

Another point to be made here is that the class $NP$ is about worst-case complexity, i.e. language $X$ can be $NP$-hard because some instances of $X$ are hard, even if they don't have any corresponding instances in $Z$.

If one has access to a polynomial algorithm solving $X$, then there exists a polynomial algorithm for $Z$. That's the main point of reductions for complexity classes. Problem $X$ is at least as hard as problem $Z$.

Another point to be made here is that the class $NP$ is about worst-case complexity, i.e. language $X$ can be $NP$-hard because some instances of $X$ are hard, even if they don't have any corresponding instances in $Z$.

Source Link
3cnf
3cnf
  • 183
  • 1
  • 9

If one has access to a polynomial algorithm solving $Z$, then there exists a polynomial algorithm for $Z$. That's the main point of reductions for complexity classes. Problem $X$ is at least as hard as problem $Z$.

Another point to be made here is that the class $NP$ is about worst-case complexity, i.e. language $X$ can be $NP$-hard because some instances of $X$ are hard, even if they don't have any corresponding instances in $Z$.