Is P Equal to NP? A Conjecture on the Difficulty of Problem Solving

  • Thread starter Thread starter Char. Limit
  • Start date Start date
  • Tags Tags
    Mean
AI Thread Summary
The discussion centers on the P vs. NP problem, which questions whether problems that can be verified quickly (NP) can also be solved quickly (P). It highlights that P represents problems solvable in polynomial time, while NP includes problems where solutions can be verified in polynomial time but not necessarily found in that time. An example illustrates this distinction by showing that while finding integer solutions to a specific equation is complex, verifying a given solution is straightforward. The prevailing belief is that P does not equal NP, indicating that easy verification does not imply easy solution. However, no definitive proof exists to confirm or refute this conjecture.
Char. Limit
Gold Member
Messages
1,222
Reaction score
23
P=NP?

to me, this suggests that N=1...
 
Mathematics news on Phys.org
it depends on what its referring to... but yeah, if 'P' & 'N' are independent variables... then N = 1...
 
P=NP is referring to two sets: P is the set of problems which can be solved with a polynomial time algorithm, and NP is the set of problems which can be checked to see if the solution is correct in polynomial time, but a solution can't be found in polynomial time.

As an example for how a distinction is natural:

For example, if I asked you to find integer solutions to the equation xy + yx=145, this would be fairly difficult. But if I tell you x=3, y=4 is a solution, it's really easy to check.

It's a famous conjecture that P is NOT equal to NP: in normal language, that just because a problem is easy to check, it doesn't mean it's easy to solve. Nobody actually has a proof one way or the other though
 

Thread 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Similar threads

I Questions regarding Kurepa's Conjecture
Replies
1
Views
2K
A P=NP: New Proof in Book from World Scientific
Replies
4
Views
2K
Insights P vs. NP conjecture and what is a Turing Machine (TM)?
Replies
6
Views
3K
Will P Ever Equal NP as Technology Advances?
Replies
5
Views
2K
Check my P=NP proof for errors (based on incompleteness of ZFC)
Replies
2
Views
2K
I Breakthrough in 3n+1 Problem: Collatz Conjecture
Replies
7
Views
5K
A Proving Goldbach's conjecture by induction (or why it doesn't seem to work)
Replies
10
Views
2K
A Show positivity and boundedness of a non-linear system
Replies
2
Views
548
Chernoff Bounds using importance sampling identity
Replies
0
Views
2K
MHB NP-Complete Problems to Reading and Understanding
Replies
4
Views
2K

Hot Threads

Recent Insights

Back
Top