Can NP-Intermediate exist if P = NP?

Posted by Jason Baker on Stack Overflow See other posts from Stack Overflow or by Jason Baker
Published on 2010-04-11T21:46:27Z Indexed on 2010/04/11 21:53 UTC
Read the original article Hit count: 277

Filed under:

complexity

|

np-complete

|

p

|

np

|

np-intermediate

My understanding is that Ladner's theorem is basically this:

P != NP implies that there exists a set NPI where NPI is not in P and NPI is not NP-complete

What happens to this theorem if we assume that P = NP rather than P != NP? We know that if NP Intermediate doesn't exist, then P = NP. But can NP Intermediate exist if P = NP?

© Stack Overflow or respective owner

Related posts about complexity

Linear complexity and quadratic complexity

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm just not sure... If you have a code that can be executed in either of the following complexities: A sequence of O(n), like for example: two O(n) in sequence O(n²) The preferred version would be the one that can be executed in linear time. Would there be a time such that the sequence… >>> More
When should complexity be removed?

as seen on Programmers - Search for 'Programmers'
Prematurely introducing complexity by implementing design patterns before they are needed is not good practice. But if you follow all (or even most of) the SOLID principles and use common design patterns you will introduce some complexity as features and requirements are added or changed to keep… >>> More
Using Completed User Stories to Estimate Future User Stories

as seen on Programmers - Search for 'Programmers'
In Scrum/Agile, the complexity of a user story can be estimated in story points. After completing some user stories, a programmer or team of programmers can use those experiences to better estimate how much time it might take to complete a future user story. Is there a methodology for breaking down… >>> More
Finding complexity of a program as a service [on hold]

as seen on Programmers - Search for 'Programmers'
I would like to find the complexity of a specific code chunk written in Java. Is there a place/web site/service where I can find out the complexity of any arbitrary program. This program might include loops/recursion. Using theory we can compute complexity ourselves. But, just curious in finding… >>> More
Form, function and complexity in rule processing

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
Tim Bass posted on ‘Orwellian Event Processing’. I was involved in a heated exchange in the comments, and he has more recently published a post entitled ‘Disadvantages of Rule-Based Systems (Part 1)’. Whatever the rights and wrongs of our exchange, it clearly failed to generate any agreement or understanding… >>> More

Related posts about np-complete

What is an NP-complete problem?

as seen on Stack Overflow - Search for 'Stack Overflow'
What is an NP-complete problem? Why is it such an important topic in computer science? >>> More
The subsets-sum problem and the solvability of NP-complete problems

as seen on Stack Overflow - Search for 'Stack Overflow'
I was reading about the subset-sums problem when I came up with what appears to be a general-purpose algorithm for solving it: (defun subset-contains-sum (set sum) (let ((subsets) (new-subset) (new-sum)) (dolist (element set) (dolist (subset-sum subsets) (setf… >>> More
Is the board game "Go" NP complete?

as seen on Stack Overflow - Search for 'Stack Overflow'
There are plenty of Chess AI's around, and evidently some are good enough to beat some of the world's greatest players. I've heard that many attempts have been made to write successful AI's for the board game Go, but so far nothing has been conceived beyond average amateur level. Could it be that… >>> More
Relating NP-Complete problems to real world problems

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a decent grasp of NP Complete problems; that's not the issue. What I don't have is a good sense of where they turn up in "real" programming. Some (like knapsack and traveling salesman) are obvious, but others don't seem obviously connected to "real" problems. I've had the experience several… >>> More
What is an NP-complete problem?

as seen on Stack Overflow - Search for 'Stack Overflow'
I tried reading previous posts about NP- My question is what does the word "COMPLETE" mean? Why is it there? What is its significance? N- Non-deterministic - makes sense' P- Polynomial - makes sense but the "COMPLETE" is still a mystery for me. >>> More