2
$\begingroup$

As the title says: are there problems in $\mathbf{NP}$ that do not reduce in polynomial time to any problem in $\mathbf{NP}$?

$\endgroup$
1
  • 2
    $\begingroup$ Only NPC (NP Complete) problems have such property they're reducible to each other in polynomial time, and a solution can be verified in polynomial time $\endgroup$
    – ShAr
    Sep 11, 2021 at 11:38

3 Answers 3

11
$\begingroup$

I understand the question as asking for the truth value of the proposition $\exists A \in \mathsf{NP}, \forall B \in \mathsf{NP}, A \not\le_p B$, where $\le_p$ denotes Karp reducibility.

Then the answer is no since, $\forall A \in \mathsf{B}$ we can pick $B=A$ and the choose the identity function as the Karp reduction from $A$ to $B$. In other words every problem in $\mathsf{NP}$ is Karp-reducible to itself.

Even if you want $A$ and $B$ to be distinct then the answer is still no. Formally, we want to know the truth value of $\exists A \in \mathsf{NP}, \forall B \in \mathsf{NP} \setminus \{A\}, A \not\le_p B$.

Indeed, for $\forall A \in \mathsf{NP}$, there exists some $B \in \mathsf{NP} \setminus \{A\}$ such that $A \le_p B$. Let $\sigma \in \Sigma$. An example of such $B$ is $\{ \sigma x \mid x \in A \}$, and the corresponding Karp reduction is $f(x) = \sigma x$.

$\endgroup$
4
  • 6
    $\begingroup$ I think your last sentence is backwards? The empty language is reducible to any non trivial language (by a reduction that always gives a constant false instance), but no non-trivial language is reducible to the empty language. $\endgroup$
    – Mjiig
    Sep 12, 2021 at 0:27
  • 1
    $\begingroup$ I take it that in the first paragraph of your answer, you interpret the “any” from the question as “some”, and in the second paragraph, you interpret it as “all”? That’s kind of confusing. $\endgroup$ Sep 12, 2021 at 11:48
  • $\begingroup$ That is, the answer does not change if you require the two problems to be distinct: just like every problem in NP is reducible to itself, every problem in NP is also reducible to a different problem in NP. $\endgroup$ Sep 12, 2021 at 11:57
  • 1
    $\begingroup$ @EmilJeřábek. Thank you! I got turned around in the second part of my answer. I revised it now. Just to be clear I understand the question as determining the truth value of: $\exists A \in \mathsf{NP}, \forall B \in \mathsf{NP}, A \not\le_p B$. Then, since we can pick $A=B$, the answer is "no". If we cannot pick $A=B$ then we are interested in the truth value of $\exists A \in \mathsf{NP}, \forall B \in \mathsf{NP} \setminus \{A\}, A \not\le_p B$. I also made the answer unambigous by removing occurrences to "any" and "all" and using formal notation instead. $\endgroup$
    – Steven
    Sep 12, 2021 at 12:41
3
$\begingroup$

The definition of the class NP-hard is that a problem is NP-hard if every problem in NP can be reduced to it in polynomial time.

The definition of the class NP-complete is just the problems that are NP-hard which are also themselves members of NP.

Therefore, since there exist members of NP-complete, the answer to your question is no, there are no problems in NP which cannot be reduced to any other problem in NP in polynomial.

In fact you can pick any one of those NP-complete problems, and there is no NP problem that cannot be reduced to that single problem of your choice.

$\endgroup$
2
  • $\begingroup$ @Steven I didn't say there are no problems which cannot be reduced to every problem in NP, I said there are no problems which cannot be reduced to any problem in NP. They can all be reduced to SAT, for example. Do you think the OP meant every rather than any? $\endgroup$
    – Ben
    Sep 12, 2021 at 10:57
  • $\begingroup$ I see! No, I think of meant it exactly the way you interpreted it. Please disregard my previous comment. $\endgroup$
    – Steven
    Sep 12, 2021 at 12:47
-4
$\begingroup$

Only NPC (NP-Complete) problems have such property they're reducible to each other in polynomial time, and a solution can be verified in polynomial time.

-For example, how can you transform a sorting instance into a Minimum Spanning Tree instance (both in P)?! Doesn't even make sense

You can search and find huge material on NPC, however this can give you a brief on the big picture

https://youtu.be/EeACNt50Wf4

A clarifying Venn diagram

enter image description here

Sometimes NPC are called the Hardest Problems as compared to those in NP-Hard

Remarks:

1-I removed the medium Venn diagram, I'm very sorry it contained wrong info, factorization, primality are considered NP-Hard in the no. of bits in the number; here is an example of a problem (IsPrime?) where verifying the correctness of a solution have the same complexity as finding the solution

2- While I was searching for a Venn diagram image to put, I found there are previous answers in the group

How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?

What is the definition of P, NP, NP-complete and NP-hard?

enter image description here From MIT lecture 2020 on complexity classes, you can watch from min44 https://youtu.be/JbafQJx1CIA

I understand that other answers address the question from the Theory of Computation point of view not from Algorithms Design & Analysis; however I still believe, at least from my view, that it's different in meaning whether they're (NP) each independently polynomial reducible to an easy instance of an NP-Hard problem or to each other, only NPC problems have that property otherwise why stated separately???

& If factorization was in P there would have been no RSA at all & many other things. It's claimed polynomial only thru Quantum Computing.

$\endgroup$
10
  • 1
    $\begingroup$ This statement is problematic. "Only NPC (NP-Complete) problems have such property they're reducible to each other in polynomial time". For example all non-trivial problems in $\mathsf{P}$ are reducible to each other in polynomial time (and it might be the case that $\mathsf{P} \neq \mathsf{NP}$). $\endgroup$
    – Steven
    Sep 11, 2021 at 14:36
  • $\begingroup$ It's most probable although not 100% sure, but not to be described "might", that P!=NP. Whether all problems in P are reducible to each other in polynomial time, I don't think so, they're each solvable in polynomial time, but that doesn't mean they can be transformed to each other; I think you mixed it up in your mind, but I'm not sure I will re-check $\endgroup$
    – ShAr
    Sep 11, 2021 at 15:12
  • 3
    $\begingroup$ The fact that all (non-trivial) problem in P can be solved in polynomial time implies that they can be reduced to each other. The reduction from a problem $A$ to a problem $B$ is easy. Let $Y$ and $N$ be some arbitrarily chosen (and fixed) "yes" and "no" instances of $B$. Solve the instance of $A$ using any polynomial-time algorithm for $A$, if the instance of $A$ was a "yes" instance then return $Y$. Otherwise return $N$. $\endgroup$
    – Steven
    Sep 11, 2021 at 15:21
  • $\begingroup$ i think that diagram would be more valuable if it showed that NPC is subset of NP. $\endgroup$
    – Effie
    Sep 11, 2021 at 15:33
  • 3
    $\begingroup$ No. I mean that the fact that the problems in $P$ are solvable in polynomial time means that they are all transformable (i.e., Karp-reducible) between one another (except for trivial problems). $\endgroup$
    – Steven
    Sep 11, 2021 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.