P vs. NP Problem: Exploring the Limit

  • Thread starter faddishworm
  • Start date
In summary, P v NP is a problem in computer science that asks whether there exists an algorithm that grows at a polynomial rate. It is not related to CPU power, and even if P = NP in the future, it would mean that it is already true today. The concept of time complexity is used to measure the efficiency of algorithms, and it is determined by the number of steps, not the number of seconds it takes. This complexity is measured by estimating the number of elementary operations needed to solve a problem and determining how fast that function grows as the input size increases.
  • #1
faddishworm
9
0
Hey All,

I was wondering if anyone had ever done any work on the P v NP problem that involved expressing P = NP as a limit

I am sure there are 1001 "proofs" submitted every day to official boards at math institutes so I thought I would come here to get a handle on the state of the problem of P and NP.

My reasoning tells me that at some point in time P will equal NP because our ability to solve problems right now is limited. If you imagine in thousands or millions of years, if we are still around surely given the rate at which we solve problems and invent technology we would be able to solve anything as quickly as we can verify it now. Bare with me I know this sounds like hocus pocus.

The RSA used to pay money if members of the public could factorize huge numbers. http://en.wikipedia.org/wiki/RSA_Factoring_Challenge

They actually had to make a few payouts because by harnessing the CPUs of thousands of machines they could compute the factors in about 6 months, despite it being computationally infeasible.

Given the rate at which CPUs get more powerful and given that they haven't been around very long is it feasible to say that at some point in time we will be able to factorize huge numbers as quickly as we can verify them?

Is it fair to say that at some point in time P = NP - is there any school of thought regarding this?
 
Mathematics news on Phys.org
  • #2
P v NP refers to whether there exists an algorithm which grows at polynomial rate. It has nothing to do with CPU power. If P = NP in a million years time in the future, that means that P = NP today.
 
  • #3
How can an algorithm grow?
 
  • #4
Wikipedia Analysis of Algorithms. Specifically Order of growth.

Another thing to point out. We use the concept of time complexity. How much "time" an algorithm uses is determined by the number of steps, not the number of seconds it takes. So even if CPUs get faster, it has no bearing on the order.
 
Last edited:
  • #5
Do you mean the time it takes an algorithm to compute something grows? or the algo itself?
 
  • #6
If n is the length of the string used as input, we estimate the number of elementary operations need to solve the problem with the algorithm. Then we get a (asymptotical) function in n. It's how fast that function grow as n approaches infinity.
 

FAQ: P vs. NP Problem: Exploring the Limit

1. What is the P vs. NP problem?

The P vs. NP problem is a major unsolved problem in computer science and mathematics. It asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. In other words, it seeks to determine whether P (problems that can be solved in polynomial time) is equal to NP (problems that can be verified in polynomial time).

2. Why is the P vs. NP problem important?

The P vs. NP problem is important because it has significant implications for the fields of computer science, mathematics, and cryptography. A proof that P is not equal to NP would have wide-reaching consequences, including showing that some problems are fundamentally more difficult to solve than others and potentially leading to new breakthroughs in algorithms and complexity theory.

3. How long has the P vs. NP problem been unsolved?

The P vs. NP problem was first proposed by mathematician Stephen Cook in 1971 and has remained unsolved for over 50 years. It is considered one of the most important open problems in computer science and has been the subject of extensive research and debate among scientists and mathematicians.

4. What progress has been made towards solving the P vs. NP problem?

While the P vs. NP problem remains unsolved, there have been significant advances and breakthroughs in related areas such as complexity theory, algorithms, and cryptography. Many researchers have devoted their careers to studying the problem, and there have been numerous attempts to prove or disprove its validity, but a definitive answer has yet to be found.

5. Is the P vs. NP problem important for practical applications?

Yes, the P vs. NP problem has practical implications for fields such as computer science, cryptography, and artificial intelligence. A resolution to the problem could lead to significant advancements in these areas, potentially making it easier to solve complex problems and improve the efficiency of algorithms used in various applications.

Similar threads

Insights P vs. NP conjecture and what is a Turing Machine (TM)?
Replies
6
Views
3K
NP vs P - difference between veryfing and answering
Replies
4
Views
3K
I Are electrons universal problem solvers?
Replies
4
Views
949
A P vs NP Guessing and process of elimination
Replies
6
Views
1K
MHB Unraveling the P vs NP Problem in Computer Science
Replies
4
Views
2K
The P vs. NP millennial prize problem
Replies
1
Views
1K
Can Freecell Algorithms Solve the P vs NP Problem?
Replies
15
Views
3K
News on an NP problem from an Amoeba
Replies
8
Views
2K
Continuous-time loop computer for NP problems?
Replies
5
Views
2K
Is the Subset Sum Problem Truly Solved by Generating Large Random Sets?
Replies
5
Views
2K

Hot Threads

Recent Insights

Back
Top