Can the Subset Sum Problem Be Solved in Polynomial Time?

  • Thread starter RagingHadron
  • Start date
In summary: You were trying to say that no algorithm can exist in polynomial time if P=NP, but you were incorrect because there is an algorithm that can exist in polynomial time if P<NP.
  • #1
RagingHadron
18
0
So I really know very little about the subject but from the little I could gather online...
Consider the subset problem on wikipedia. Does a subset of {−2, −3, 15, 14, 7, −10} equal zero? It shows the work for you and then says that no algorithm to find it in polynomial time is known, only in exponential (with (2^n)-1 tries) It says that an algorithm can only exist in polynomial time if P=NP. So now, can we not set (2^n)-1=n^x so that the algorithm in polynomial time is n^((log((2^n)-1)+2i∏c)/(log(n)) where c∈Z, Z being the set of integers. Does that make any sense?
 
Technology news on Phys.org
  • #2
RagingHadron said:
So I really know very little about the subject but from the little I could gather online...
Consider the subset problem on wikipedia.
http://en.wikipedia.org/wiki/Subset-sum_problem
RagingHadron said:
Does a subset of {−2, −3, 15, 14, 7, −10} equal zero?
As you have written this, it doesn't make sense. Each subset of some other set is itself a set, and a set is not equal to a number. The actual description is "is there a non-empty subset whose sum is zero?"
RagingHadron said:
It shows the work for you and then says that no algorithm to find it in polynomial time is known, only in exponential (with (2^n)-1 tries) It says that an algorithm can only exist in polynomial time if P=NP. So now, can we not set (2^n)-1=n^x so that the algorithm in polynomial time is n^((log((2^n)-1)+2i∏c)/(log(n)) where c∈Z, Z being the set of integers. Does that make any sense?
 
  • #3
Mark44 said:
The actual description is "is there a non-empty subset whose sum is zero?"

Yeah that's what I meant. But what was wrong with the rest of it?
 
  • #4
Which wikipedia article were you reading? I provided a link to the one I thought you were referring to, but I don't see in that one some of what you're talking about.
 
  • #5
It was in the p versus np problem page specifically, http://en.m.wikipedia.org/wiki/P_versus_NP_problem here. It's in the third paragraph. But was the work that I did correct/incorrect? I'm sure that there's a flaw in my approach to the problem somewhere seeing as it's so simple...
 
  • #6
Never mind, I saw what my flaw was.
 

FAQ: Can the Subset Sum Problem Be Solved in Polynomial Time?

What is the P=NP problem?

The P=NP problem is a mathematical problem in computer science that asks whether every problem that can be quickly verified by a computer can also be quickly solved by a computer. In simpler terms, it is asking if there is an efficient way to solve difficult problems.

Why is the P=NP problem important?

The P=NP problem is important because it has real-world implications for computer science and cryptography. If P=NP is proven to be true, it would mean that many complex problems could be solved efficiently, leading to significant advancements in technology. However, if P does not equal NP, it would mean that there are some problems that are fundamentally difficult to solve, which has implications for encryption and security.

What does the "subset problem" refer to in relation to P=NP?

The "subset problem" refers to a specific subset of the P=NP problem. It is asking whether, given a set of numbers and a target number, there is an efficient way to determine if there is a subset of those numbers that adds up to the target number. This is a well-known and difficult problem in computer science, and it is believed that it falls under the category of NP-complete problems.

Why is the P=NP problem considered unsolved?

The P=NP problem is considered unsolved because, despite decades of research and numerous attempts, no one has been able to definitively prove whether P equals NP or not. It is an open problem in computer science and is considered one of the most important unsolved problems in the field.

What are some potential consequences of solving the P=NP problem?

If the P=NP problem is solved, it would have significant consequences for various industries and fields. It could lead to more efficient algorithms and solutions for complex problems, revolutionizing technology and science. It could also have implications for cryptography and security, as it could potentially make certain encryption methods obsolete. Additionally, it could have economic impacts, as solving P=NP could lead to advancements and innovations that could drive economic growth.

Similar threads

MHB Explaining Time Complexity and NP Problems
Replies
17
Views
4K
Challenge: Find the minimum amount of draws possible for a list of integers
Replies
9
Views
2K
MHB Program to calculate the sum of polynomials
Replies
4
Views
1K
Why are hash maps constant time?
Replies
13
Views
3K
What makes a problem computationally NP?
Replies
10
Views
3K
MHB Booth algorithm for multiplying signed numbers
Replies
1
Views
1K
How Can We Efficiently Parallelize the N-Queens Problem?
Replies
11
Views
2K
MHB How to Multiply Two Polynomials Using Divide-and-Conquer Algorithms?
Replies
1
Views
1K
Understanding busy beavers (noncomputability)
Replies
2
Views
1K
Why is this matrix not working in my program?
Replies
9
Views
1K

Hot Threads

Recent Insights

Back
Top