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

  • Context: Graduate 
  • Thread starter Thread starter Char. Limit
  • Start date Start date
  • Tags Tags
    Mean
Click For Summary
SUMMARY

The discussion centers on the P vs NP problem, a fundamental question in computer science regarding the relationship between problems that can be solved in polynomial time (P) and those for which solutions can be verified in polynomial time (NP). Participants highlight that while NP problems can be easily verified, finding solutions is often significantly more challenging. The prevailing belief is that P is not equal to NP, although no definitive proof exists to confirm this conjecture. The example of finding integer solutions to the equation xy + yx=145 illustrates the distinction between solving and verifying solutions.

PREREQUISITES
  • Understanding of polynomial time algorithms
  • Familiarity with computational complexity theory
  • Knowledge of NP-completeness
  • Basic algebra and problem-solving skills
NEXT STEPS
  • Research the implications of the P vs NP conjecture on cryptography
  • Explore NP-complete problems and their significance
  • Learn about polynomial time reductions and their role in complexity theory
  • Investigate current approaches and attempts to prove or disprove P=NP
USEFUL FOR

This discussion is beneficial for computer scientists, mathematicians, and anyone interested in theoretical computer science and the complexities of algorithmic problem-solving.

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
 

Similar threads

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