What does it mean to say

  • #1
Char. Limit
Gold Member
1,204
14
P=NP?

to me, this suggests that N=1...
 

Answers and Replies

  • #2
1,254
3
it depends on what its referring to.... but yeah, if 'P' & 'N' are independent variables... then N = 1.....
 
  • #3
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,540
581
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
 

Related Threads on What does it mean to say

  • Last Post
Replies
6
Views
2K
Replies
7
Views
3K
  • Last Post
Replies
15
Views
9K
Replies
10
Views
398
  • Last Post
Replies
1
Views
1K
Replies
1
Views
4K
Replies
10
Views
2K
Replies
5
Views
15K
Replies
1
Views
569
Replies
3
Views
725
Top