Answers.Body: <p>It seems <a href="https://www.lesswrong.com/posts/wmhgGRW5QLHEtFRST/computation-complexity-of-agi-design" rel="nofollow noreferrer">this post</a> 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 <span class="math-container">$P = NP$</span> 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!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-28T12:45:15.193Z
Answers.LastActivityDate: 2022-06-28T12:45:15.193Z
Answers.UserDisplayName: OmG
Body: <p><span class="math-container">$P$</span> vs <span class="math-container">$NP$</span> is a famous problem. We generally believe <span class="math-container">$P\neq NP$</span>. However suppose there is a polynomial time algorithm of order say <span class="math-container">$O((n+m)^2)$</span> or <span class="math-container">$O((n+m)^3)$</span> (a low degree polynomial complexity with small hidden constants) for <span class="math-container">$n$</span> variable SAT problem in <span class="math-container">$m$</span> clauses, then what consequence would it have on <span class="math-container">$AI$</span> and machine learning? Would <span class="math-container">$AGI$</span> be any closer?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-27T21:31:44.023Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-27T23:41:50.910Z
Comments.Text: I have specified quadratic or cubic complexity and have specifically mentioned low degree polynomial with small hidden constants complexity.
Comments.UserDisplayName: Justaperson
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-28T23:01:10.203Z
Comments.Text: See [this post](https://ai.stackexchange.com/q/15986/2444) too.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-03-21T21:37:03.693Z
Comments.Text: -1 what a nonsense. P vs NP from https://en.wikipedia.org/wiki/Theory_of_computation and AGI are not related at all.
Comments.UserDisplayName: Quonux
Tags: <machine-learning><agi><computational-complexity>
Title: What consequence would a polynomial time algorithm for SAT have on AGI?
UserDisplayName: Justaperson
ThreadText: # What consequence would a polynomial time algorithm for SAT have on AGI?
  
  (Asked by: username_0 on 2022-06-27)
  
  $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?
  
  **Tags:** machine-learning, agi, computational-complexity
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: I have specified quadratic or cubic complexity and have specifically mentioned low degree polynomial with small hidden constants complexity.  
  > **username_1**: See [this post](https://ai.stackexchange.com/q/15986/2444) too.  
  > **username_2**: -1 what a nonsense. P vs NP from https://en.wikipedia.org/wiki/Theory_of_computation and AGI are not related at all.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2022-06-28. Score: 0
  
  It seems [this post](https://www.lesswrong.com/posts/wmhgGRW5QLHEtFRST/computation-complexity-of-agi-design) 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!
  
  
  ---
  
  