[Math] Can every problem in NP be exponentially reduced to any other problem in NP

computational complexitycomputer sciencenp-complete

A and B are both problems in NP.
Does a function f that transforms any instance of A into an instance of B and function F that transforms the solution to that instance of B into solution to problem A exist?

Basically, is the following true?
$$A,B \in NP$$
$$\{ \exists f,F\ |\ A(x) = F(f(A(x))),\ f(A(x))=B(y)\}$$

This answer indicates that polynomial reduction is possible if both A and B are in P and I'd like to know it something similar occurs in NP as well.

I'm aware that a polynomial reduction would mean P=NP (and vice versa) and that a reduction of problem in NP to a problem in NP-complete is possible in polynomial time, but I wonder if even if P $\neq$ NP, some form of transformation is still be possible.

Thank you

Best Answer

Any problem in NP can be solved in exponential time because $NP\subseteq EXPTIME$.

https://en.wikipedia.org/wiki/EXPTIME

So the answer of this question would be the same as the answer you linked for two problems in P.

Related Solutions

[Math] NP hard/complete

I would say that the concept of 'nondeterminism' is one of the great red herrings in the discussion of NP-complete problems. To my mind it's much better to think of a problem's being in NP as a criterion for confirming solutions; 'if we're given a hypothetical solution instance for a problem, can we verify it in polynomial time?'. Seen this way, a lot of problems in NP become a lot clearer: for instance, Satisfiability (of a boolean expression) is verified just by plugging in the purported assignment to all the variables of the expression and confirming that the result is true; the Traveling Salesman Problem can be verified by confirming that a proposed route gets to all cities, doesn't go to any city more than once, and has total length under the requisite bound; etc. All of these obviously take polynomial time to confirm. 'Exponential solvability' is really a red-herring; it happens that there's an obvious exponential-time algorithm for NP-complete problems (use our polynomial-time checking algorithm on each of the exponentially-many possible solution instances), but the exponentiality isn't really at the heart of these problems; it's just an expression of the size of the search space. Seen this way, the P vs. NP question becomes 'if we can efficiently confirm a solution, can we efficiently find a solution?' - but this has nothing to do with exponential-time problems in and of itself.

NP-Complete – How to Prove that P ? NP

What would be if I be able to prove that one of the NP-Complete problems cannot be solved in polynomial time.

I assume you mean "problems cannot be solved in polynomial time on a deterministic Turing machine". NP, after all, stands for "nondeterministic polynomial", and includes the decision problems that can be solved in polynomial time on a nondeterministic Turing machine.

What would be if I be able to prove that one of the NP-Complete problems cannot be solved in polynomial time [on a deterministic Turing machine].

Then you would prove that all the $\rm NP\text{-}complete$ problems have no deterministic polynomial-time algorithms.

Proof by contradiction:

Imagine we have some algorithm, $A$, can solve some $\rm NP\text{-}complete$ problem, $S$.
Let us call your "one of the $\rm NP\text{-}complete$ problems" $R$.
Accordingly, $R$ cannot be solved in polynomial time (deterministically); because you have some given proof.
Since they are both $\rm NP\text{-}complete$ problems, then by Cook reductions, we can reduce $R\stackrel{...}{\rightarrow} S$ in polynomial time (deterministically).
Then we can use $A(S)$ and solve $S$. This is a contradiction to $(3)$.

Is there any problem that been proven to be in NP and not in P?

I am not sure what you are actually trying to ask here, but here is a summary on the complexity classes.

$\rm \mathbf P$: is the class of decision problems that can can be solved in polynomial time (deterministically).

There are several equivalent ways of looking at $\rm NP$.

$\rm \mathbf{NP}$:

is the class of decision problems that can be solved in polynomial time on a nondeterministic Turing machine.
is the class of decision problems for which one can easily verify the solutions of their corresponding optimization problems (which are also proofs of the decision).

The two explanations above are intuitively equivalent: The non-determinism of a NTM can use the verifiability of the answer to "try all solutions" and only keep the one that successfully verifies.

$\rm {NP}$ obviously includes all of $\rm P$.

$\rm \mathbf{NP\text{-}complete}$: is the class of decision problems that are the hardest problems in $\rm NP$. These problems have reductions each-other. Indeed, all of $\rm P$ and $\rm NP$ can be reduced to any $\rm NP\text{-}complete$ problem.

$\rm\mathbf{P}$ vs $\rm\mathbf{NP}$: is the question about whether the $\rm NP\text{-}complete$ class of problems can be solved as fast as the problems in $\rm P$; in other words, does nondeterminism make a machine "faster" (in the sense of polynomial-time=fast, superpolynomial-time=slow).

$\rm\mathbf{NP\text{-}hard}$: are the set of decision problems (some definitions include search and optimization problems) that are at least as hard as $\rm NP\text{-}complete$ problems. So, all $\rm NP\text{-}complete$ are also $\rm NP\text{-}hard$ problems.

A nice picture from wikipedia:

enter image description here

So back to your question:

Is there any problem that been proven to be in NP and not in P?

EDIT: Just to be clear, I understood this to mean:

Is there any problem that been proven to be in NP and [proven] not [to be] in P?

The answer is NO, because that would imply $\rm P\ne NP$. Proof by contradiction:

Imagine $\rm P=NP$
Imagine there is a problem, $R$ that is in $\rm NP$, but not in $\rm P$.
$\rm NP\text{-}complete$ problems are the hardest in $\rm NP$ (all problems in NP can indeed be reduced to any $\rm NP\text{-}complete$ problem).
All $\rm NP\text{-}complete$ problems must be at least as hard as $R$, which follows from $(2,3)$.
All $\rm NP\text{-}complete$ problems are not in $\rm P$, as $R$ is not in $\rm P$, and $\rm NP\text{-}complete$ problems hare harder than $R$ ( from $(2,4)$ ). Therefore $\rm NP \not\in P$, thus $\rm P\ne NP$. This contradicts $(1)$.

Best Answer

Related Solutions

[Math] NP hard/complete

NP-Complete – How to Prove that P ? NP

Related Question