Are there any P problems that were previously NP-Complete?

  • (5 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »

61 Replies - 7349 Views - Last Post: 31 December 2013 - 12:47 AM

#1 sim0nk   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 3
  • Joined: 29-January 13

Are there any P problems that were previously NP-Complete?

Posted 09 October 2013 - 11:04 AM

Repeating the subject: Are there any P problems that were previously NP-Complete?
This is pretty interesting to know and examine I think.
Is This A Good Question/Topic? 0
  • +

Replies To: Are there any P problems that were previously NP-Complete?

#2 mostyfriedman   User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Are there any P problems that were previously NP-Complete?

Posted 09 October 2013 - 11:41 AM

If that were the case, then all of them would be in P :). To clarify, NP-complete problems are all equivalent, meaning that if there's an algorithm to solve one of them in polynomial time, then there's an algorithm to solve all of them in polynomial time. So to answer your question, no. If it were the case, then we would be able to decrypt passwords very quickly.

This post has been edited by mostyfriedman: 09 October 2013 - 11:43 AM

Was This Post Helpful? 2
  • +
  • -

#3 sim0nk   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 3
  • Joined: 29-January 13

Re: Are there any P problems that were previously NP-Complete?

Posted 09 October 2013 - 12:06 PM

Oh yes, I've realised this before you posted your answer, doh x]
My question can actually can be reduced to P ?= NP :P

What I meant actually was: what problems today can be solved in polynomial time that previously only had greater than polynomial time solution algorithms. I mean from the time Compute Science was just born.
Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11651
  • View blog
  • Posts: 19,801
  • Joined: 19-March 11

Re: Are there any P problems that were previously NP-Complete?

Posted 09 October 2013 - 12:38 PM

Matrix multiplication comes to mind. Look up Strassen's algorithm.

People are also finding ways to finess even NP-complete problems. You might want to take a look at the lectures in the last two weeks of Tim Roughgarden's Algorithms 2 course (currently running). He has some good discussions of NP-complete problems and practical approaches to dealing with them. (I'm trying to sort out his Travelling Salesman problem set right now - it's a little tricky)
Was This Post Helpful? 2
  • +
  • -

#5 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12646
  • View blog
  • Posts: 45,819
  • Joined: 27-December 08

Re: Are there any P problems that were previously NP-Complete?

Posted 09 October 2013 - 03:33 PM

The classes P and NP deal with Turing Machines and language recognition. If a language L is in P, there exists a deterministic Turing Machine that will accept or reject an arbitrary string in L in polynomial time.

If a language L is in NP, then we are dealing with non-deterministic Turing Machines. That means that if a string is in L, then the NDTM will end in a halting accepting state in polynomial time. If the string is not in L, then the NDTM may halt in a non-accepting halting state or it may just keep running.

Problems are reduced to languages for the purpose of computability.
Was This Post Helpful? 0
  • +
  • -

#6 Fooality   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 12-December 13

Re: Are there any P problems that were previously NP-Complete?

Posted 12 December 2013 - 03:33 AM

Absolutely there are, but its a matter of how you phrase the problem in many cases. Consider the question: "Are there any problems solvable in logarithmic time that were previously only solvable in linear time?" Then think of finding a name in a sorted list. The inefficient way is to compare the query against every name (linear time) the efficient way is to use binary search (log time). For an individual learning programming, the problem is at first linear time, then log time as they learn more, even though the problem hasn't changed at all. We just got more information on how it can be solved.

I actually just had a problem where my best solution was in non-polynomial time, until I found a way to do it in polynomial time. There were a sufficient amount of repetitions (the same code running many times) and they were predictable, so I could multiply the found answers instead of computing the same thing over and over, reducing it to N^3 time.

If there were some clear reason a problem that was previously NP could NEVER be solved in P, then it would be certain that P != NP. But its a conjecture, it remains unproven. How many steps a problem takes to solve is only known (at this point) to God, so its wise to not to believe our best solution is THE best solution.
Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11651
  • View blog
  • Posts: 19,801
  • Joined: 19-March 11

Re: Are there any P problems that were previously NP-Complete?

Posted 12 December 2013 - 06:06 AM

Quote

How many steps a problem takes to solve is only known (at this point) to God, so its wise to not to believe our best solution is THE best solution.


There are many provable bounds. Sorting a list takes O(n log n), and that's provable. You're not going to do better by trying harder.
Was This Post Helpful? 1
  • +
  • -

#8 Fooality   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 12-December 13

Re: Are there any P problems that were previously NP-Complete?

Posted 12 December 2013 - 03:02 PM

View Postjon.kiparsky, on 12 December 2013 - 06:06 AM, said:

Quote

How many steps a problem takes to solve is only known (at this point) to God, so its wise to not to believe our best solution is THE best solution.


There are many provable bounds. Sorting a list takes O(n log n), and that's provable. You're not going to do better by trying harder.


Be that as it may, often the bounds are not proven. My point is its easy to use more steps than needed to solve a real world problem: Simple example, suppose I tell you I need you to find the shortest route between all the cities on a map, and all the cities are in a strait line. If you're silly, you use the algorithm used to solve travelling salesman, and it takes NP time. If you're not, you draw a line through all the cities, knowing that's the shortest route. In that case the faster solution is obvious, but there are other cases, where hidden constraints on the configuration of cities mean a solution outside of NP exists, but its a really big question as to whether or not we can notice or find it.
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12646
  • View blog
  • Posts: 45,819
  • Joined: 27-December 08

Re: Are there any P problems that were previously NP-Complete?

Posted 12 December 2013 - 03:09 PM

Quote

but there are other cases, where hidden constraints on the configuration of cities mean a solution outside of NP exists,

This doesn't make any sense. How can it be outside of NP?

Also, a problem falling into P or (more generally) NP is a statement about the problem, not an arbitrary instance. You can't say "I can do solve one instance of the TSP in a few steps, thus this instance isn't in NP." That's not how it works. The TSP problem is NP-Complete, even if you can solve arbitrary instances.
Was This Post Helpful? 1
  • +
  • -

#10 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11651
  • View blog
  • Posts: 19,801
  • Joined: 19-March 11

Re: Are there any P problems that were previously NP-Complete?

Posted 12 December 2013 - 03:11 PM

Quote

If you're silly, you use the algorithm used to solve travelling salesman, and it takes NP time. If you're not, you draw a line through all the cities, knowing that's the shortest route.


That is not a solution to the TSP. That is a solution to a trivial TSP instance. To be a solution, it would have to cover the actual travelling salesman problem, which is not restricted to small graphs easily represented on the plane.

The travelling salesman is certainly in NP, and provably so. (proofs are not hard to find - for example, check wikipedia)
It is possible to find good heuristics for special cases, but that doesn't mean the general case isn't NP-hard. That is, the bounds are in fact proven. If you can show that those proofs are not good, you can pretty much write your own ticket, so if you really believe what you're saying you should get to work proving it.
Was This Post Helpful? 1
  • +
  • -

#11 Fooality   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 12-December 13

Re: Are there any P problems that were previously NP-Complete?

Posted 12 December 2013 - 04:59 PM

View Postjon.kiparsky, on 12 December 2013 - 03:11 PM, said:

Quote

If you're silly, you use the algorithm used to solve travelling salesman, and it takes NP time. If you're not, you draw a line through all the cities, knowing that's the shortest route.


That is not a solution to the TSP. That is a solution to a trivial TSP instance. To be a solution, it would have to cover the actual travelling salesman problem, which is not restricted to small graphs easily represented on the plane.

The travelling salesman is certainly in NP, and provably so. (proofs are not hard to find - for example, check wikipedia)
It is possible to find good heuristics for special cases, but that doesn't mean the general case isn't NP-hard. That is, the bounds are in fact proven. If you can show that those proofs are not good, you can pretty much write your own ticket, so if you really believe what you're saying you should get to work proving it.


Let me clarify what I'm saying a little more. Suppose we have an algorithm A(n) = S(L(n)), and we want to know how long it takes for a given n. L(n) is an algorithm which generates a list R of locations on a 2D cartesian plane. S® finds the shortest path between all of them.

Now notice the temptation to classify this as NP, because a S® would have to solve the travelling salesman problem, for all possible lists R. However, its completely possible that the range of L(n) only includes lists which are solvable in P time, (like if all the locations always lay on a line) though in practice it may be very, very difficult to figure this out. Regardless, once you do, then the problem was which appeared only solvable in NP time, is now solvable in P time. So a problem went from NP to P, by getting more information about the problem. So that's an example what the OP was asking about.

View Postmacosxnerd101, on 12 December 2013 - 03:09 PM, said:

Quote

but there are other cases, where hidden constraints on the configuration of cities mean a solution outside of NP exists,

This doesn't make any sense. How can it be outside of NP?

Also, a problem falling into P or (more generally) NP is a statement about the problem, not an arbitrary instance. You can't say "I can do solve one instance of the TSP in a few steps, thus this instance isn't in NP." That's not how it works. The TSP problem is NP-Complete, even if you can solve arbitrary instances.


Sorry, wreckless wording there. I meant a solution inside P exists. please see my post above, for an example of what I'm talking about. And sorry apparently
S(R)

without the code tags becomes S®. New to the forum.
Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12646
  • View blog
  • Posts: 45,819
  • Joined: 27-December 08

Re: Are there any P problems that were previously NP-Complete?

Posted 12 December 2013 - 05:03 PM

But you're still talking about an instance of the problem, not the general problem as a whole. P and NP say something about the problem. If you want to talk about runtime complexities (Big-O, Big-Omega, Big-Theta), those would better describe the problem.

If we're talking about showing a problem (not an instance of a problem) is in P, one way to do this is with a log-space reduction to a P-complete language. Log-space implies polynomial time, but the converse does not hold (that we know of, otherwise, we would have P = NP). If you look at it in terms of languages, you have to reduce ALL the strings in the language to a P-Complete language to show the problem exists in P. If you are dealing with a subset of the language (ie., an instance of the problem), you are saying nothing about whether or not the problem is in P or NP.
Was This Post Helpful? 0
  • +
  • -

#13 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11651
  • View blog
  • Posts: 19,801
  • Joined: 19-March 11

Re: Are there any P problems that were previously NP-Complete?

Posted 12 December 2013 - 05:10 PM

Okay, to clarify a liitle more: if the problem isn't the travelling salesman problem, as in the case you describe, then it may well not be in NP. Fine, we're agreed on that. However, by restricting yourself to a special case, you've gone from talking about an NP problem to talking about a very different problem - you might think of this as a TSP-1, a Travelling Salesman in Abbott's "Lineland".

We should point out that this problem still takes a little more work than you seem to think. We still have to put the points in order so we can describe the path, so we're sorting, which implies O(n log n) minimum. That's if we know in advance that we're looking at a line. If we need to notice that we're looking at a line, I would imagine that the problem is harder, though I don't know the order of complexity off the top of my head.

And I see that, of course, while I've been typing this Mac has scooped me once again. Oh, well.


Anyway, the point is, what's changed in the situation you describe is the problem, not its complexity. I would suggest, if you have plenty of spare time, that you might want to take a peek at Jeff Ullman's Automata Theory course on Coursera. This will lead you up to a more effective understanding of the NP-complete languages. (and it's nice in that it's very self-contained. There's almost nothing that you need to know going in, all of the primitives outside of some very basic logic and set theory are constructed in the early lectures)
Was This Post Helpful? 2
  • +
  • -

#14 AdamSpeight2008   User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Are there any P problems that were previously NP-Complete?

Posted 12 December 2013 - 05:23 PM

Sorting using comparisions is O(n Log n). If you don't use comparisons (eg Radix / BIRST) its linear O(n).

This post has been edited by AdamSpeight2008: 12 December 2013 - 05:24 PM

Was This Post Helpful? 0
  • +
  • -

#15 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11651
  • View blog
  • Posts: 19,801
  • Joined: 19-March 11

Re: Are there any P problems that were previously NP-Complete?

Posted 12 December 2013 - 05:27 PM

Yeah, I'm familiar with radix sort. My favorite sort, actually. However, it's pretty useless for most cases so I don't usually bring it up. For example, the preprocessing needed to apply it to a set of points defined in 2D or 3D space would eat up the time advantages pretty nicely.
Was This Post Helpful? 0
  • +
  • -

  • (5 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »