Skip to main content
Computer Science

Return to Answer

typo fix
Source Link
Joe
Joe
  • 4.1k
  • 1
  • 20
  • 38

A problem in $X$ is not $X$-complete if there are any other problems in $X$ which cannot be reduced to it. One straightforward (but possibly only effective on trivial examples) method would be proving your problem is also in some other complexity class $Y$ such that $Y \subset X$.

For example, if you want to show that your problem is not $EXPTIME$ complete, then it is sufficient to show that it is in $P$, since $P \subsetneq EXPTIME$. However, it if you wanted to show that a problem is not $NP$-complete, then it is not necessarily sufficient to show that it is in $P$, since it is not known whether or not $P = NP$.

A problem in $X$ is not $X$-complete if there are any other problems in $X$ which cannot be reduced to it. One straightforward (but possibly only effective on trivial examples) method would be proving your problem is also in some other complexity class $Y$ such that $Y \subset X$.

For example, if you want to show that your problem is not $EXPTIME$ complete, then it is sufficient to show that it is in $P$, since $P \subsetneq EXPTIME$. However, it if you wanted to show that a problem is not $NP$-complete, then it is not necessarily sufficient to show that it is in $P$, since it is not known whether or not $P = NP$.

A problem in $X$ is not $X$-complete if there are any other problems in $X$ which cannot be reduced to it. One straightforward (but possibly only effective on trivial examples) method would be proving your problem is also in some other complexity class $Y$ such that $Y \subset X$.

For example, if you want to show that your problem is not $EXPTIME$ complete, then it is sufficient to show that it is in $P$, since $P \subsetneq EXPTIME$. However, if you wanted to show that a problem is not $NP$-complete, then it is not necessarily sufficient to show that it is in $P$, since it is not known whether or not $P = NP$.

added 1 characters in body
Source Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393

A problem in $X$ is not $X$-complete if there are any other problems in $X$ which cannot be reduced to it. One straightforward (but possibly only effective on trivial examples) method would be proving your problem is also in some other complexity class $Y$ such that $Y \subset X$.

For example, if you want to show that your problem is not $EXPTIME$ complete, then it is sufficient to show that it is in $P$, since $P \subsetneq EXPTIME$. However, it if you wanted to show that a problem is not $NP$-competecomplete, then it is not necessarily sufficient to show that it is in $P$, since it is not known whether or not $P = NP$.

A problem in $X$ is not $X$-complete if there are any other problems in $X$ which cannot be reduced to it. One straightforward (but possibly only effective on trivial examples) method would be proving your problem is also in some other complexity class $Y$ such that $Y \subset X$.

For example, if you want to show that your problem is not $EXPTIME$ complete, then it is sufficient to show that it is in $P$, since $P \subsetneq EXPTIME$. However, it if you wanted to show that a problem is not $NP$-compete, then it is not necessarily sufficient to show that it is in $P$, since it is not known whether or not $P = NP$.

A problem in $X$ is not $X$-complete if there are any other problems in $X$ which cannot be reduced to it. One straightforward (but possibly only effective on trivial examples) method would be proving your problem is also in some other complexity class $Y$ such that $Y \subset X$.

For example, if you want to show that your problem is not $EXPTIME$ complete, then it is sufficient to show that it is in $P$, since $P \subsetneq EXPTIME$. However, it if you wanted to show that a problem is not $NP$-complete, then it is not necessarily sufficient to show that it is in $P$, since it is not known whether or not $P = NP$.

Source Link
Joe
Joe
  • 4.1k
  • 1
  • 20
  • 38

A problem in $X$ is not $X$-complete if there are any other problems in $X$ which cannot be reduced to it. One straightforward (but possibly only effective on trivial examples) method would be proving your problem is also in some other complexity class $Y$ such that $Y \subset X$.

For example, if you want to show that your problem is not $EXPTIME$ complete, then it is sufficient to show that it is in $P$, since $P \subsetneq EXPTIME$. However, it if you wanted to show that a problem is not $NP$-compete, then it is not necessarily sufficient to show that it is in $P$, since it is not known whether or not $P = NP$.