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

### #1

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

Posted 09 October 2013 - 11:04 AM

This is pretty interesting to know and examine I think.

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

### #2

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

Posted 09 October 2013 - 11:41 AM

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

### #3

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

Posted 09 October 2013 - 12:06 PM

My question can actually can be reduced to P ?= NP

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.

### #4

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

Posted 09 October 2013 - 12:38 PM

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)

### #5

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

Posted 09 October 2013 - 03:33 PM

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.

### #6

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

Posted 12 December 2013 - 03:33 AM

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.

### #7

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

Posted 12 December 2013 - 06:06 AM

Quote

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.

### #8

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

Posted 12 December 2013 - 03:02 PM

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

Quote

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.

### #9

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

Posted 12 December 2013 - 03:09 PM

Quote

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.

### #10

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

Posted 12 December 2013 - 03:11 PM

Quote

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.

### #11

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

Posted 12 December 2013 - 04:59 PM

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

Quote

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.

macosxnerd101, on 12 December 2013 - 03:09 PM, said:

Quote

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.

### #12

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

Posted 12 December 2013 - 05:03 PM

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.

### #13

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

Posted 12 December 2013 - 05:10 PM

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)

### #14

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

Posted 12 December 2013 - 05:23 PM

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

### #15

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

Posted 12 December 2013 - 05:27 PM