1
$\begingroup$

$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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Jun 27, 2022 at 21:31
  • $\begingroup$ I have specified quadratic or cubic complexity and have specifically mentioned low degree polynomial with small hidden constants complexity. $\endgroup$ Jun 27, 2022 at 23:41
  • $\begingroup$ See this post too. $\endgroup$
    – nbro
    Jun 28, 2022 at 23:01

1 Answer 1

0
$\begingroup$

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!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .