5
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Your questions basically restate the P vs. NP question. If the answer to question 1 is yes then P $=$ NP. If the answer to question 2 is "exponential" then P $\neq$ NP. $\endgroup$
    – Kyle Jones
    Dec 8, 2016 at 19:07
  • $\begingroup$ If the answer to question 1 is 'yes' and 2 is 'exponential' then $P \neq NP$. I know this(in part why I asked). However even if the answer to question 1 is yes, and question 2 is polynomial, (at least by my meagre CS knowledge) it does not prove $P = NP$. As that is only one problem out if a much larger set of NP problems. However it will challenge the belief that $P \neq NP$. Whatever valid answer I receive, progress willb be made on $P$ vs $NP$. $\endgroup$
    – Tobi Alafin
    Dec 8, 2016 at 19:15
  • $\begingroup$ That said while it is possible to prove $P \neq NP$. How might one to attempt to prove $P = NP$? $\endgroup$
    – Tobi Alafin
    Dec 8, 2016 at 19:19
  • 2
    $\begingroup$ This site isn't for what you seem to want to use it for. This site isn't for opinion polls, collecting lists of examples, soliciting discussion, or open-ended calls to participation. See our help center for details on question types that aren't appropriate here (because they don't work well here). $\endgroup$
    – D.W. ♦
    Dec 8, 2016 at 20:28
  • $\begingroup$ @TobiAlafin, a possible proof of P=NP would be to find a polynomial-time solution to any NP-hard problem, e.g. SAT. $\endgroup$
    – Paul Draper
    Oct 8, 2018 at 10:29

1 Answer 1

Reset to default
6
$\begingroup$

  1. 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.

  2. 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$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ ANY answer to my question will be informative. It will either prove $P \neq NP$, or challenge the belief that $P \neq NP$. $\endgroup$
    – Tobi Alafin
    Dec 8, 2016 at 19:21
  • $\begingroup$ "There's a $O$(n) lower bound on every problem." What about binary searches? Aren't they logarithmically lower bounded. $\endgroup$
    – Tobi Alafin
    Dec 8, 2016 at 19:24
  • 1
    $\begingroup$ @TobiAlafin: "basically" every problem. Anything $O(1)$ obviously doesn't have an $O(n)$ bound, and things also change depending on your model of computation (i.e. tape or RAM machine) $\endgroup$
    – jmite
    Dec 8, 2016 at 19:46
  • 5
    $\begingroup$ @TobiAlafin Also, you won't get any answers to $P$ vs $NP$. Nobody knows the answer! So I guarantee you 100% that nothing anyone will say here will prove $P \neq NP$. As for challenging that belief, there's no proof on either side, so nobody could give something that can challenge the belief either. The most educated opinion is to abstain from having one until a proof of one or the other is discovered. You can have intuitions one way or another, but these are inherently unfounded. $\endgroup$
    – jmite
    Dec 8, 2016 at 19:49
  • $\begingroup$ @AndrásSalamon my bad, it's fixed now! $\endgroup$
    – jmite
    Dec 9, 2016 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.