0 like 0 dislike
0 like 0 dislike
I have a question about the p-np problem. If a p-np problem is assumed to be np-hard, why do both true and false problems arise?

2 Answers

0 like 0 dislike
0 like 0 dislike
As best I can tell, I think your issue is that you don’t know the proper definition for “problem” which P=NP is talking about.

The short version is that “the p-np problem” is NOT the type of problem which this field of math (Complexity Theory) talks about. The P=NP problem is asking “is every NP set also a P set?” I don’t think this can be phrased as a problem of the same type (a set of numbers).

One of the ways to prove P=NP is to show that some NP-hard problem (a problem at least as hard as any NP problem) is a P problem. You seem to understand this. But P=NP is not an NP problem- it isn’t even really the type of problem which can be classified as P or NP or anything like that.

Let me know if this did or didn’t make any sense.

If it helps, here’s a vastly oversimplified version of what P=NP means: “if there’s a hint I can give you that makes a problem easy, does that mean the problem, even without the hint, was easy already?”
0 like 0 dislike
0 like 0 dislike
Complexity classes like P and NP are used to classify problems that take in some sort of input and return a yes-or-no answer based on that input. For example, the traveling salesman problem takes in a list of cities (with associated distances between them), and the answer will depend on those cities. The P-NP problem is not of that type, since there's no input parameter that the answer depends on: it's just a single yes-or-no question. So the P-NP problem isn't the sort of thing that we would usually classify as P, NP, or any such complexity class.

Related questions

0 like 0 dislike
0 like 0 dislike
8 answers
limecordiale asked Jun 21
How do you solve for the values of a so that det(A) = 0? I’m trying to do this using the cofactor expansion method but I’m getting a very convoluted algebraic equatio...
limecordiale asked Jun 21
0 like 0 dislike
0 like 0 dislike
2 answers
Figure1 asked Jun 21
What does Euler characteristic tell us about topological spaces? For example, what do we find out from the fact that the Euler characteristic of a sphere is 2 and of a to...
Figure1 asked Jun 21
by Figure1
0 like 0 dislike
0 like 0 dislike
4 answers
itsWoodrow asked Jun 21
What did I do wrong? I was pretty confident about my answers until I got the results and apparently only got 16, 18, and 20 correct.
itsWoodrow asked Jun 21
0 like 0 dislike
0 like 0 dislike
1 answer
Sharon_McGowan_ asked Jun 21
How do you go about solving 7c of which I can solve basic Pascal questions and my attempt of 7d is as below though I don’t know how to
Sharon_McGowan_ asked Jun 21
0 like 0 dislike
0 like 0 dislike
59 answers
timor_sv asked Jun 21
Got about a free 50-60 days before joining my PhD. Any advice or suggestions on what to do in this free time ?
timor_sv asked Jun 21

24.8k questions

103k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!