Will P Ever Equal NP as Technology Advances?

  • Thread starter Thread starter faddishworm
  • Start date Start date
AI Thread 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 'Video on imaginary numbers and some queries'

Thread 'Video on imaginary numbers and some queries'

Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
View full post »
Thread 'Unit Circle Double Angle Derivations'

Thread 'Unit Circle Double Angle Derivations'

Here I made a terrible mistake of assuming this to be an equilateral triangle and set 2sinx=1 => x=pi/6. Although this did derive the double angle formulas it also led into a terrible mess trying to find all the combinations of sides. I must have been tired and just assumed 6x=180 and 2sinx=1. By that time, I was so mindset that I nearly scolded a person for even saying 90-x. I wonder if this is a case of biased observation that seeks to dis credit me like Jesus of Nazareth since in reality...
View full post »

Thread 'Fermat's Last Theorem'

Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
View full post »

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
1K
What are the implications if P=NP in Artificial Intelligence?
Replies
4
Views
5K
Continuous-time loop computer for NP problems?
Replies
5
Views
2K
MHB Unraveling the P vs NP Problem in Computer Science
Replies
4
Views
2K
News on an NP problem from an Amoeba
Replies
8
Views
2K
A Shinichi Mochizuki's ABC Conjecture and Replication Crisis in Maths
Replies
33
Views
7K
Understanding the P vs NP Problem: Factoring and Its Impact on Internet Security
Replies
3
Views
7K
A Finding Minimal Mean Distance Curves on the Unit Sphere
Replies
2
Views
2K

Hot Threads

Recent Insights

Back
Top