$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?
Asked
Active
Viewed 195 times
1 Answers
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,866
- 12
- 19