Does anyone know of a problem previously believed to be NP hard, to be solved nowadays in polynomial time optimally?
$\begingroup$
$\endgroup$
7
-
8$\begingroup$ By “previously known as”, do you mean “previously (and erroneously) believed to be”? $\endgroup$– LarrySnyder610Sep 2, 2019 at 12:04
-
3$\begingroup$ Because if it’s NP, it’s NP forever — it doesn’t change category. $\endgroup$– LarrySnyder610Sep 2, 2019 at 12:05
-
1$\begingroup$ Not exactly what you're asking, but related: whether there was a polynomial time solution to the primality testing problem was unknown for some time and is now known to be solvable in polynomial time with the AKS algorithm. However, no-one has or had a valid proof that this problem is NP-hard. $\endgroup$– Discrete lizardSep 2, 2019 at 14:09
-
1$\begingroup$ See What are examples of problems that were believed to be NP-complete but are actually P?. $\endgroup$– TheSimpliFire ♦Sep 2, 2019 at 15:07
-
2$\begingroup$ Can't see why all the downvotes - it's a bit vague but this is a very interesting question. $\endgroup$– Nikos KazazakisSep 2, 2019 at 22:58
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
4
This is an answer to the original question before it was edited (Can a problem move from NP to P).
No, if a problem is NP-complete then it is not solvable in polynomial time unless P=NP, which has not been proven yet. Furthermore, if there were any NP-hard problem which would be solvable in polynomial time then (by reduction) it could be used to solve any other problem in NP, thus implying P=NP.
-
1$\begingroup$ I don't believe that would be as you say necessarily. Just because you can solve a problem, or a group of problems, in polynomial time, doesn't mean that you can solve all problems in polynomial time. How the P vs NP question arose if we know all the problems that are NP cannot be solved in polynomial time? $\endgroup$ Sep 2, 2019 at 13:53
-
8$\begingroup$ @dimboukosis That claim YukiJ makes here follows directly from the definition of NP-hardness. I suggest you have a look at an introduction to P, NP and NP-hardness. I can recommend this answer on CS.SE. $\endgroup$ Sep 2, 2019 at 13:57
-
$\begingroup$ @YukiJ Your answer is answering the original version of the question, which seemed to be asking whether a problem can "move" from NP to P. The current version of the question is asking whether there are problems that were believed to be in NP but later discovered to be in P. Would you mind just adding a brief note in your answer indicating that your answer pertains to the original version of the question? $\endgroup$ Sep 4, 2019 at 3:03
-
1
$\begingroup$
$\endgroup$
8
Does anyone know of one problem that is NP hard, but can now be solved in polynomial time optimally?
Wikipedia has this to say about NP-completeness:
"In computational complexity theory, a problem is NP-complete when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm.
...
A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it, and a problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If any NP-complete problem has a polynomial time algorithm, all problems in NP do.".
It's not a one size fits all, solve one you've solved them all, type of problem/solution.
It's a case of discovering one of the many difficult problems that can be solved by a new technique, and the applicability of using the same (or similar) methods to solve similar problems (not categorically every problem, or stating the equality of one set of problems to another).
There are a few hard problems that now can be solved in polynomial time, or faster.
It has been proven and demonstrated, using a new architecture, that the subset-sum problem has been solved using standard microelectronic technology in a laboratory setting.
See: "Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states" (July 7 2015), by Fabio L. Traversa, Chiara Ramella, Fabrizio Bonani, and Massimiliano Di Ventra:
"Memcomputing is a novel non-Turing paradigm of computation that uses interacting memory cells (memprocessors for short) to store and process information on the same physical platform. It was recently proved mathematically that memcomputing machines have the same computational power of non-deterministic Turing machines. Therefore, they can solve NP-complete problems in polynomial time and, using the appropriate architecture, with resources that only grow polynomially with the input size.
...
Here, we show an experimental demonstration of an actual memcomputing architecture that solves the NP-complete version of the subset-sum problem in only one step ($T = 1/f_0$) and is composed of a number of memprocessors that scales linearly with the size of the problem. We have fabricated this architecture using standard microelectronic technology so that it can be easily realized in any laboratory setting.".
...
Another hard problem is the Planted ($L, \Delta$) motif search (PMS) problem and the quorum PMP where the motif needs to occur in at least $Q$ of the $N$ strings.
References:
"A Survey on Applications and Architectural-optimizations of Micron's Automata Processor", Article in Journal of Systems Architecture · July 2019, DOI: 10.1016/j.sysarc.2019.07.006
"3.1 Bioinformatics
“Planted (L, ∆) motif search problem” (PMP): For $N$ strings, each of length $M$, PMP finds a motif of length $L$ that occurs in all the strings with at most $\Delta$ mismatches [8]. For example, let the input strings be $\text{GATCAGTTCAC}$, $\text{TAAGACGGTCA}$ and $\text{AGTCTCTCGAG}$, and $L = 4$ and $\Delta = 1$. Then the motif $\text{CTCA}$ is present in all the three strings. Here, the motif itself need not be exactly present in any string, which is what happens in this case. PMP can be generalized to the “quorom PMP” (qPMP), where the motif needs to occur in at least $Q$ of the $N$ strings. PMP and hence, qPMP are NP-hard problems [8]. PMP is useful in domains such as DNA and protein sequencing.".[8]I. Roy and S. Aluru, “Finding motifs in biological sequences using the Micron automata processor", in Parallel and Distributed Processing Symposium, 2014 IEEE 28th International, 2014, pp. 415–424."An Overview of Micron’s Automata Processor" by Ke Wang, Kevin Angstadt, Chunkun Bo, Nathan Brunelle, Elaheh Sadredini, Tommy Tracy II, Jack Wadden, Mircea Stan, Kevin Skadron, Dept. of Comp. Sci., Dept. of Elec. & Comp. Eng. University of Virginia
Included image:
Figure 2 – Testing Board of Micron’s Automata processor. Click for a labeled diagram. The production model has the FPGA upgraded to Arria 10 GX270, uses a PCIe 3.0x8 connector and has 4 GB DDR3 32 bit @ 533 MHz. The SODIMM boards have four chips on each side.
Micron sold their Automata Processor IP to Natural Intelligence, whom licenses usage to the University of Virginia.
Videos:
YouTube: "Micron's Automata Processor" - Micron
YouTube: "Micron Showcases Automata Processor for Big Data" - RichReport
Vimeo: "Webinar2.1 - Introductions.Skadron.final" - UVA Computer Science
Other: "Algorithmic Techniques for Solving Graph Problems on the Automata Processor", by Indranil Roy, Nagakishore Jammula and Srinivas Aluru, Published in: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Date of Conference: 23-27 May 2016, DOI: 10.1109/IPDPS.2016.116
-
3$\begingroup$ It should be noted that this does not imply P=NP, because we are not using a Turing computer. Examples of using analog computing to solve NP-hard problems also appear on the P-versus-NP page by Gerhard Woeginger. See for example number 14 on the list which mentions solving the Steiner Tree problem by dipping glass plates in a soap solution. $\endgroup$ Sep 3, 2019 at 14:29
-
3$\begingroup$ The claims made by the Memcomputing people are not really accepted by computer science experts, see this question on cs theory stackexchange, and in particular this blog post by Scot Aaronson. $\endgroup$ Sep 3, 2019 at 20:39
-
4$\begingroup$ I'd rather read a solid reasoned argument why Scott Aaronson's well-argued and well-explained criticism is incorrect, than a bunch of general endorsements on an arXiv profile not directly related to the claim made. Even respectable authors can make claims that turn out to be incorrect when scrutinized in more detail, so I believe it is better to focus on the argument than on someone's accolades. $\endgroup$ Sep 3, 2019 at 22:51
-
2$\begingroup$ @Rob There appear to be more articles questioning the claims of Traversa et al. For example, this paper and this paper conclude that they rely on the provision of unphysical resources (these papers also cite Aaronson's blog post btw). $\endgroup$ Sep 4, 2019 at 7:16
-
2$\begingroup$ Best quote from Scott's blogpost: >>For computer scientists ultimately came to realize that all proposals along these lines simply "smuggle the exponentiality" somewhere that isn’t being explicitly considered, exactly like all proposals for perpetual-motion machines smuggle the entropy increase somewhere that isn’t being explicitly considered.<< $\endgroup$– JakobSSep 4, 2019 at 8:02