4
$\begingroup$

I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=NP" problem, but I was wondering whether there were any particular instances when people were close to it. I've also heard about the factoring number problem being solved by a quantum computer by Shor's algorithm. Would this count as an algorithm which solved an NP-problem in polynomial time please ? Please do ask if you want me to clarify any parts in my questions. Thanks in advance.

$\endgroup$
7
  • 3
    $\begingroup$ In particular, the third point in the above link: Restrict the problem, i.e., If you can make more assumptions on your inputs, the problem may become easy. $\endgroup$ – Inuyasha Yagami May 3 at 18:02
  • 1
    $\begingroup$ Yeah, several times, but they have all been recruited by the Laundry. $\endgroup$ – Peter - Reinstate Monica May 3 at 20:22
  • 4
    $\begingroup$ "I know this dabbles into the "does P=NP" problem" -- it seems like it is the P = NP problem. Also -- factoring is not known to be NP-hard. In fact, it is conjectured to not be. There are of course plenty of NP problems (one of the things you ask about) which have been solved in polynomial time, namely those in P itself (which is a subset of NP). $\endgroup$ – John Coleman May 3 at 23:27
  • 1
    $\begingroup$ There's an open million dollar prize for anyone who can demonstrate this, so rest assured you'll hear about it the moment someone does. $\endgroup$ – J... May 4 at 17:39
  • 2
    $\begingroup$ To clarify, many NP-hard problems can be solved in polynomial time on a nondeterministic Turing Machine. That's exactly what the NP-Complete problems are. The question is whether they can also be solved in P-time on a deterministic Turing Machine. Quantum computers aren't exactly nondeterministic Turing Machines, but they aren't equivalent to Turing Machines, either, and so P-time quantum algorithms don't show that a problem is in P. $\endgroup$ – Ray May 4 at 18:57
10
$\begingroup$

By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then $P=NP$. So, short answer is - no.

However, its possible to think instead of solving the problems fully, to approximate a solution, or to solve them randomly. There are attempts at attacking from those points of view, but they are not perfect at all. Randomization isn't known to help "as-is", and many NP-hard problems are known that are also hard to approximate (finding an approximation will yield $P=NP$)

There are also attemps taking a look at notions much stronger than the usual turing machine. For instance, the quantum computer can be considered one. Another obvious example is the non-deterministic turing machines, in which - by definition - $NP$ would be in polynomial time.

$\endgroup$
2
  • $\begingroup$ I heard that quantum computers cover a different area though and they don't count. Something like BQP? $\endgroup$ – MathIsFun May 3 at 11:43
  • 2
    $\begingroup$ yes, it is defined as a different computational model and a different complexity class. I don't know a lot about it, but BQP is the polynomial version in the quantum computer model. Just like BPP is the polynomial version in a randomized TM $\endgroup$ – nir shahar May 3 at 11:45
5
$\begingroup$

If the answer to the first question were to be yes, then $P=NP$, as stated in nir shahar's answer. This has not been done.

"The easiest NP hard problem"

However you next asked if any NP-hard problems have been solved in close to polynomial time, for which you might love to learn about what has been called "The easiest NP hard problem" because there's a pseudo-polynomial time solution using dynamic programming, and there are heuristics that solve the problem in many cases, sometimes optimally. The problem is the partitioning problem: Decide whether a set of positive integers can be partitioned into two sets such that the sum of the numbers in one set equal the sum of the numbers in the first set. Despite it being an NP-complete problem, it can be solved quite efficiently, as for example described in this PDF.

$\endgroup$
4
$\begingroup$

Strictly speaking, as the other answers explain, no. A polynomial-time algorithm for an NP-hard problem is not known nor expected to exist. But I think your underlying question is whether or not there are examples of natural NP-hard problems that are, in some sense, easier to solve than some other NP-hard problems.

There are several flavors in which you can quantify the hardness of NP-hard problems more closely. For example, there are problems that are extremely difficult to approximate (e.g., maximum clique) while some problems we can approximate arbitrarily close (e.g., knapsack). You could also have a look at exact algorithms: there are natural problems for which the best algorithms run in time $O^*(2^n)$ and there is some evidence no algorithms faster than that exists, while others admit runtimes of roughly $O^*(2^\sqrt{n})$ (e.g., planar problems) or even better. Or, you could look at parameterized complexity, where the idea is to do a two-dimensional analysis, i.e., take not only the size of the input $n$ but also pick some additional parameter, such as solution size or some structural parameter $k$. Then, some problems admit algorithms whose runtime is of the form $f(k) n^{O(1)}$, where $f$ is some computable function depending only on $k$, while some problems don't (e.g., $k$-clique).

$\endgroup$
2
$\begingroup$

The other answers are correct, but f I may add an observation: it seems like you are conflating classes of problems and particular instances. There are a number of instances that can be solved in polynomial time in classes that are NP-hard in general. For instance, Boolean satisfiability is NP-hard in general, since it reduces to 3SAT. However, there are a bunch of instances called Horn clauses which can actually be solved in linear time. Notice that these instances are a subset of all instances of SAT. If you do not know whether the instance you have to solve is a Horn clause, the problem is NP-hard. If you do know that your instances are restricted that way, you have HORNSAT, which is in P. It all depends what your input potentially could be, and complexity goes by the worst-case instance.

$\endgroup$

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.