Will P Ever Equal NP as Technology Advances?

  • Thread starter Thread starter faddishworm
  • Start date Start date
Click For Summary
The discussion centers on the P vs NP problem and the possibility of P equaling NP as technology advances. Participants explore the idea that future advancements in computational power might eventually allow for problems to be solved as quickly as they can be verified. However, it is emphasized that the fundamental nature of P vs NP is not solely dependent on CPU speed but rather on the existence of polynomial-time algorithms. The conversation also highlights the distinction between time complexity and actual computation time, noting that improvements in hardware do not change the theoretical growth rates of algorithms. Ultimately, the consensus suggests that while technological advancements may enhance problem-solving capabilities, they do not alter the underlying mathematical principles of the P vs NP problem.
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.
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

Similar threads

Insights P vs. NP conjecture and what is a Turing Machine (TM)?
  • · Replies 6 ·
Replies
6
Views
3K
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
Continuous-time loop computer for NP problems?
  • · Replies 5 ·
Replies
5
Views
2K
MHB Unraveling the P vs NP Problem in Computer Science
  • · Replies 4 ·
Replies
4
Views
2K
News on an NP problem from an Amoeba
  • · Replies 8 ·
Replies
8
Views
2K
Graduate Shinichi Mochizuki's ABC Conjecture and Replication Crisis in Maths
  • · Replies 33 ·
2
Replies
33
Views
7K
Understanding the P vs NP Problem: Factoring and Its Impact on Internet Security
  • · Replies 3 ·
Replies
3
Views
7K
Graduate Finding Minimal Mean Distance Curves on the Unit Sphere
  • · Replies 2 ·
Replies
2
Views
2K