Skip to main content
Computer Science

Return to Question

big Omega is probably more fitting for lower bounds
Source Link
edit approved Dec 30, 2021 at 17:46
user3840170
edit approved Dec 30, 2021 at 17:46
user3840170
  • 123
  • 6

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the degree of the polynomial run time is very large (e.g. $O(n^{10000})$$\Omega(n^{10000})$) such that any reasonably large problem is still out of reach for our current computing technology.

My question is: is it possible to find/construct a problem that have a lower-bound polynomial complexity $O(n^p)$$\Omega(n^p)$ to compute but an upper bound $O(n^q)$ to verify, with $q$ being quite small (e.g. $q=1$) and $p\gg q$. This problem would function essentially the same as current problems for which no known polynomial algorithms exist (e.g. factorization), and thus would still be usable in e.g. security systems in even in the case of $P=NP$.

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the degree of the polynomial run time is very large (e.g. $O(n^{10000})$) such that any reasonably large problem is still out of reach for our current computing technology.

My question is: is it possible to find/construct a problem that have a lower-bound polynomial complexity $O(n^p)$ to compute but an upper bound $O(n^q)$ to verify, with $q$ being quite small (e.g. $q=1$) and $p\gg q$. This problem would function essentially the same as current problems for which no known polynomial algorithms exist (e.g. factorization), and thus would still be usable in e.g. security systems in even in the case of $P=NP$.

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the degree of the polynomial run time is very large (e.g. $\Omega(n^{10000})$) such that any reasonably large problem is still out of reach for our current computing technology.

My question is: is it possible to find/construct a problem that have a lower-bound polynomial complexity $\Omega(n^p)$ to compute but an upper bound $O(n^q)$ to verify, with $q$ being quite small (e.g. $q=1$) and $p\gg q$. This problem would function essentially the same as current problems for which no known polynomial algorithms exist (e.g. factorization), and thus would still be usable in e.g. security systems in even in the case of $P=NP$.

Became Hot Network Question
Source Link
zyl1024
zyl1024
  • 462
  • 4
  • 13

Problems that are polynomially "hard" to compute but "easy" to verify

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the degree of the polynomial run time is very large (e.g. $O(n^{10000})$) such that any reasonably large problem is still out of reach for our current computing technology.

My question is: is it possible to find/construct a problem that have a lower-bound polynomial complexity $O(n^p)$ to compute but an upper bound $O(n^q)$ to verify, with $q$ being quite small (e.g. $q=1$) and $p\gg q$. This problem would function essentially the same as current problems for which no known polynomial algorithms exist (e.g. factorization), and thus would still be usable in e.g. security systems in even in the case of $P=NP$.