Skip to main content
Computer Science

Return to Answer

Ridiculous typo
Source Link
Niel de Beaudrap
Niel de Beaudrap
  • 4.2k
  • 1
  • 18
  • 32

By the nondeterministic spacetime hierarchy, you could show that the problem is $\mathsf {NEXP}$-hard; as $\mathsf {NP} \ne \mathsf {NEXP}$, it is impossible to reduce the problem in polynomial time to any problem in $\mathsf {NP}$, so the problem will not be in $\mathsf {NP}$.

However, if your problem is not nearly that difficult, you may be hard-pressed to prove that it is not in $\mathsf {NP}$; and if it is in $\mathsf {NP}$, you'll be hard-pressed to show that $\mathsf {NP}$ is not Karp-reducible to your problem without assuming that $\mathsf P \ne \mathsf {NP}$.

By the nondeterministic space hierarchy, you could show that the problem is $\mathsf {NEXP}$-hard; as $\mathsf {NP} \ne \mathsf {NEXP}$, it is impossible to reduce the problem in polynomial time to any problem in $\mathsf {NP}$, so the problem will not be in $\mathsf {NP}$.

However, if your problem is not nearly that difficult, you may be hard-pressed to prove that it is not in $\mathsf {NP}$; and if it is in $\mathsf {NP}$, you'll be hard-pressed to show that $\mathsf {NP}$ is not Karp-reducible to your problem without assuming that $\mathsf P \ne \mathsf {NP}$.

By the nondeterministic time hierarchy, you could show that the problem is $\mathsf {NEXP}$-hard; as $\mathsf {NP} \ne \mathsf {NEXP}$, it is impossible to reduce the problem in polynomial time to any problem in $\mathsf {NP}$, so the problem will not be in $\mathsf {NP}$.

However, if your problem is not nearly that difficult, you may be hard-pressed to prove that it is not in $\mathsf {NP}$; and if it is in $\mathsf {NP}$, you'll be hard-pressed to show that $\mathsf {NP}$ is not Karp-reducible to your problem without assuming that $\mathsf P \ne \mathsf {NP}$.

**NEXP**-hardness is enough -- no need for completeness.
Source Link
David Richerby
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

By the nondeterministic space hierarchy, you could show that the problem is $\mathsf {NEXP}$-complete;hard; as $\mathsf {NP} \ne \mathsf {NEXP}$, it is impossible to reduce the problem in polynomial time to any problem in $\mathsf {NP}$, so the problem will not be in $\mathsf {NP}$.

However, if your problem is not nearly that difficult, you may be hard-pressed to prove that it is not in $\mathsf {NP}$; and if it is in $\mathsf {NP}$, you'll be hard-pressed to show that $\mathsf {NP}$ is not Karp-reducible to your problem without assuming that $\mathsf P \ne \mathsf {NP}$.

By the nondeterministic space hierarchy, you could show that the problem is $\mathsf {NEXP}$-complete; as $\mathsf {NP} \ne \mathsf {NEXP}$, it is impossible to reduce the problem in polynomial time to any problem in $\mathsf {NP}$, so the problem will not be in $\mathsf {NP}$.

However, if your problem is not nearly that difficult, you may be hard-pressed to prove that it is not in $\mathsf {NP}$; and if it is in $\mathsf {NP}$, you'll be hard-pressed to show that $\mathsf {NP}$ is not Karp-reducible to your problem without assuming that $\mathsf P \ne \mathsf {NP}$.

By the nondeterministic space hierarchy, you could show that the problem is $\mathsf {NEXP}$-hard; as $\mathsf {NP} \ne \mathsf {NEXP}$, it is impossible to reduce the problem in polynomial time to any problem in $\mathsf {NP}$, so the problem will not be in $\mathsf {NP}$.

However, if your problem is not nearly that difficult, you may be hard-pressed to prove that it is not in $\mathsf {NP}$; and if it is in $\mathsf {NP}$, you'll be hard-pressed to show that $\mathsf {NP}$ is not Karp-reducible to your problem without assuming that $\mathsf P \ne \mathsf {NP}$.

Source Link
Niel de Beaudrap
Niel de Beaudrap
  • 4.2k
  • 1
  • 18
  • 32

By the nondeterministic space hierarchy, you could show that the problem is $\mathsf {NEXP}$-complete; as $\mathsf {NP} \ne \mathsf {NEXP}$, it is impossible to reduce the problem in polynomial time to any problem in $\mathsf {NP}$, so the problem will not be in $\mathsf {NP}$.

However, if your problem is not nearly that difficult, you may be hard-pressed to prove that it is not in $\mathsf {NP}$; and if it is in $\mathsf {NP}$, you'll be hard-pressed to show that $\mathsf {NP}$ is not Karp-reducible to your problem without assuming that $\mathsf P \ne \mathsf {NP}$.