1

$P$ vs $NP$ is a famous problem. We generally believe $P\neq NP$. However suppose there is a polynomial time algorithm of order say $O((n+m)^2)$ or $O((n+m)^3)$ (a low degree polynomial complexity with small hidden constants) for $n$ variable SAT problem in $m$ clauses, then what consequence would it have on $AI$ and machine learning? Would $AGI$ be any closer?

Justaperson
  • 153
  • 3
  • I would rewrite the title to be "what consequences would P=NP have on AI?", because right now it seems that you're asking any polynomial time algorithms and there are many. – nbro Jun 27 '22 at 21:31
  • I have specified quadratic or cubic complexity and have specifically mentioned low degree polynomial with small hidden constants complexity. – Justaperson Jun 27 '22 at 23:41
  • See [this post](https://ai.stackexchange.com/q/15986/2444) too. – nbro Jun 28 '22 at 23:01

1 Answers1

0

It seems this post could be an answer to your question. In sum, it says that AGI is more related to interactional complexity than classical complexity. Therefore, these two are perpendicular concepts to each other. However, the consequence of $P = NP$ might affect that some problems in AGI will be more fastly computed, but there is no way in that sense to show whether AGI has been achieved or not!

OmG
  • 1,731
  • 10
  • 19