Will P Ever Equal NP as Technology Advances?

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

Discussion Overview

The discussion revolves around the P vs NP problem, specifically exploring the implications of technological advancements on the relationship between P and NP. Participants examine whether future improvements in computational power could lead to P equaling NP, and the nature of algorithm growth and time complexity.

Discussion Character

  • Debate/contested
  • Technical explanation
  • Conceptual clarification

Main Points Raised

  • One participant suggests that as technology advances, it may eventually be possible for P to equal NP, arguing that our current limitations might be overcome in the distant future.
  • Another participant counters that the P vs NP question is independent of computational power, asserting that if P were to equal NP in the future, it would imply that P equals NP today.
  • A question is raised about the concept of algorithm growth, prompting further clarification on how time complexity is defined and measured.
  • Participants discuss the distinction between the time it takes for an algorithm to compute a solution and the algorithm's growth in terms of input size.
  • There is mention of estimating the number of operations required by an algorithm based on the input length, leading to a function that describes growth as input size increases.

Areas of Agreement / Disagreement

Participants express differing views on the relationship between technological advancement and the P vs NP problem. There is no consensus on whether future computational capabilities could influence the fundamental nature of P and NP.

Contextual Notes

Some assumptions about the nature of algorithms and time complexity are not fully explored, and the discussion does not resolve the implications of technological advancements on theoretical computer science.

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
9K
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