Will P Ever Equal NP as Technology Advances?

  • Context: Graduate 
  • Thread starter Thread starter faddishworm
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on the P vs NP problem, specifically the hypothesis that P may eventually equal NP due to advancements in technology and computational power. Participants explore the implications of time complexity and algorithm growth, emphasizing that the existence of polynomial-time algorithms is independent of CPU speed. The RSA Factoring Challenge is cited as an example of how collective computational efforts can solve problems previously deemed infeasible, raising questions about future capabilities in problem-solving. The conversation highlights the distinction between time complexity and actual computation time, reinforcing that algorithm efficiency is determined by the number of steps rather than the speed of processors.

PREREQUISITES
  • Understanding of P vs NP problem in computational theory
  • Familiarity with time complexity and algorithm growth
  • Knowledge of polynomial-time algorithms
  • Basic concepts of computational power and its limitations
NEXT STEPS
  • Research the implications of the P vs NP problem on cryptography
  • Explore advancements in algorithm design and their impact on computational theory
  • Study the RSA Factoring Challenge and its significance in computational complexity
  • Investigate the concept of time complexity in various algorithms
USEFUL FOR

Mathematicians, computer scientists, and anyone interested in theoretical computer science, particularly those exploring the implications of algorithm efficiency and computational limits.

faddishworm
Messages
9
Reaction score
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
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.
 
How can an algorithm grow?
 
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:
Do you mean the time it takes an algorithm to compute something grows? or the algo itself?
 
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.
 

Similar threads

Insights P vs. NP conjecture and what is a Turing Machine (TM)?
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad NP vs P - difference between veryfing and answering
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Are electrons universal problem solvers?
  • · Replies 4 ·
Replies
4
Views
1K
What are the implications if P=NP in Artificial Intelligence?
  • · Replies 4 ·
Replies
4
Views
5K
Graduate P vs NP Guessing and process of elimination
  • · Replies 6 ·
Replies
6
Views
2K
MHB Unraveling the P vs NP Problem in Computer Science
  • · Replies 4 ·
Replies
4
Views
2K
Continuous-time loop computer for NP problems?
  • · Replies 5 ·
Replies
5
Views
2K
Graduate Shinichi Mochizuki's ABC Conjecture and Replication Crisis in Maths
  • · Replies 33 ·
2
Replies
33
Views
8K
News on an NP problem from an Amoeba
  • · Replies 8 ·
Replies
8
Views
2K
Graduate Understanding the P vs NP Problem: Factoring and Its Impact on Internet Security
  • · Replies 3 ·
Replies
3
Views
7K