5
$\begingroup$

Let $X$ be some problem known to be in $NP$. What is the natural next step in exploring the complexity of the problem? Is it trying to prove whether it is in $P$ or try to prove it is $NP$-Hard? Taking the example of the Graph-isomorphism problem it seems to me that after discovering that problem is in $NP$. It is not easy to decide what to do next. Some people suggest me to prove it into $NP \cap CoNP$.

Question : What is worth to try if it is only known that problem is in $NP$? Is there any sequence (like first $NP$, $NP$-Hard, ....) to explore the complexity of the problem?

$\endgroup$

2 Answers 2

5
$\begingroup$

So you have found out $X \in \mathbf{NP}$. Unfortunately, as Juho hints at in their answer, there is no "list" you can systematically go over to try and investigate $X$ further. This is mainly because separation results in complexity theory are (yet) few and far between, so most of the things you may try will not explicitly fail; you'll only be unsuccessful. For example, if you try to show $X \in \mathbf{P}$ you might succeed, but if it turns out to be incorrect it is very unlikely you will be able to prove it (since then $\mathbf{P} \neq \mathbf{NP}$).

This lack of "feedback" means you should tackle $X$ from different perspectives, and it is only experience (and a good deal of luck!) which will give you a "hunch" as to where the most promising one is. The following are a few options you might consider, as well as their implications if you manage to prove or disprove them (if any). Note I am only considering structural complexity theory here (which seems to be what you are interested in), but by all means this is what the entirety of complexity theory is about. Depending on the structure of $X$, it is also possible to consider $X$ from a parameterized complexity point of view, or try to find subexponential algorithms for it (see also number 4 below), and so forth and so on.

  1. $X$ is $\mathbf{NP}$-complete

    Prove: This is basically the end of the line for investigating $X$. It is also not a very surprising result since the list of $\mathbf{NP}$-complete problems is huge (and it already was when Richard Karp started to compile this list).

    Disprove: Congratulations! You have proved $\mathbf{P} \neq \mathbf{NP}$.

  2. $X \in \mathbf{P}$

    Prove: This is the second most likely outcome and even more unsurprising than the former.

    Disprove: Congratulations! You have proved $\mathbf{P} \neq \mathbf{NP}$.

  3. $X \in \mathbf{coNP}$

    Prove: Then $X$ is in $\mathbf{NP} \cap \mathbf{coNP}$ (which, for instance, includes factoring). Reconsider $X \in \mathbf{P}$.

    Disprove: Congratulations! You have proved $\mathbf{NP} \neq \mathbf{coNP}$.

  4. $X \in \mathbf{GI}$ (the graph isomorphism class)

    Prove: Then $X$ admits a quasipolynomial-time algorithm (and is unlikely to be $\mathbf{NP}$-complete). Reconsider $X \in \mathbf{P}$.

    Disprove: Congratulations! You have proved $\mathbf{P} \subseteq \mathbf{GI} \neq \mathbf{NP}$

  5. $X \in \mathbf{BPP}$

    Prove: Since it is widely suspected that $\mathbf{BPP} = \mathbf{P}$, this is only interesting if $X \in \mathbf{P}$ is not obvious. Consider also $X \in \mathbf{RP}$ or even $X \in \mathbf{ZPP}$.

    Disprove: Congratulations! You have proved $\mathbf{NP} \neq \mathbf{BPP}$ (and quite likely also $\mathbf{P} \neq \mathbf{NP}$).

And the list goes on and on. As you can see, disproving any of these options leads to separation results, all of which would be major breakthroughs and, thus, unlikely to be proven simply by considering a random problem $X \in \mathbf{NP}$. This means you cannot expect to go through this list from head to tail making ticks and crosses as you go; you have to "guess" which of the options (if any!) is more likely and (with some luck) you'll be able to prove it.

$\endgroup$
3
$\begingroup$

It depends, you should try to do whatever the problem smells like. You will need experience to get a good hunch.

It's also not uncommon to try to do both. You might start by trying to come up with a polynomial time algorithm. Getting stuck? Why is that? Could you simulate that in an NP-hardness proof? Or you might start by building an NP-hardness proof from a "nearby problem" that has similar characteristics. While playing around with suitable gadgets you might realize things like "oh, any algorithm will always have to do this when encountering this type of subgraph..."

This earlier answer talks more about the art of finding reductions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.