principleMinor
Lower bounds and $P$ vs $NP$
Viewed 0 times
lowerboundsand
Problem
I know $P$ vs $NP$ is an open problem in Computer Science. However the people concerned (at least according to Wikipedia) believe $P \neq NP$.
I have two questions:
$(1.)$ Given that it is possible to prove lower bounds for problems. Does there exist any problem(s) for which the solution can be verified in polynomial time but no known algorithm can solve it in polynomial time which has a proven lower bound?
$(2.)$ Is this proven lower bound polynomial or exponential?
I have two questions:
$(1.)$ Given that it is possible to prove lower bounds for problems. Does there exist any problem(s) for which the solution can be verified in polynomial time but no known algorithm can solve it in polynomial time which has a proven lower bound?
$(2.)$ Is this proven lower bound polynomial or exponential?
Solution
-
Every $NP$-complete problem is an example of this! It's just a question of how good the lower bounds are.
For example, there's an $\Omega(n)$ lower bound on basically every problem, since you need to read your entire input to solve it. This is a very imprecise lower bound, but it does exist.
So, you're not going to get a good list of a bunch of problems like this, because such a list would be too large, and uninformative.
Whether there are problems with notable lower bounds is a different issue. I don't know of any that fit your criteria (sorting is the most famous one, but it's in $P$). Here's an example question about bounds on 3SAT:
Not very informative, as you can see.
-
The known lower bounds in such a case will always be polynomial. If there were any problems verifiable in polynomial time (in $NP$) with an exponential lower bound, that would imply that $P \neq NP$.
Every $NP$-complete problem is an example of this! It's just a question of how good the lower bounds are.
For example, there's an $\Omega(n)$ lower bound on basically every problem, since you need to read your entire input to solve it. This is a very imprecise lower bound, but it does exist.
So, you're not going to get a good list of a bunch of problems like this, because such a list would be too large, and uninformative.
Whether there are problems with notable lower bounds is a different issue. I don't know of any that fit your criteria (sorting is the most famous one, but it's in $P$). Here's an example question about bounds on 3SAT:
- https://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat
Not very informative, as you can see.
-
The known lower bounds in such a case will always be polynomial. If there were any problems verifiable in polynomial time (in $NP$) with an exponential lower bound, that would imply that $P \neq NP$.
Context
StackExchange Computer Science Q#67118, answer score: 6
Revisions (0)
No revisions yet.