Artificial Intelligence Stack Exchange
Artificial Intelligence Stack Exchange

Questions tagged [computational-complexity]

The amount of resources required to run a given algorithm in relation to a given task.

https://en.wikipedia.org/wiki/Computational_complexity

36 questions
35
votes
7 answers

What are examples of promising AI/ML techniques that are computationally intractable?

To produce tangible results in the field of AI/ML, one must take theoretical results under the lens of computational complexity. Indeed, minimax effectively solves any two-person "board game" with win/loss conditions, but the algorithm quickly…
k.c. sayz 'k.c sayz'
  • 2,061
  • 10
  • 26
6
votes
1 answer

What does "hard for AI" look like?

In theoretical computer science, there is a massive categorization of the difficulty of various computational problems in terms of their asymptotic worst-time computational complexity. There doesn't seem to be any analogous analysis of what problems…
Stella Biderman
  • 271
  • 1
  • 13
4
votes
1 answer

Is time/space estimation of possible actions required for creating an AGI?

Given infinite resources/time, one could create AGIs by writing code to simulate infinite worlds. By doing that, in some of the worlds, AGIs would be created. Detecting them would be another issue. Since we don't have infinite resources, the most…
Răzvan Flavius Panda
  • 141
  • 6
4
votes
1 answer

Would it take 1700 years to run AlphaGo Zero in commodity hardware?

From this link, AlphaGo would take millennia to run in regular hardware. They generated 29 million games for the final result, which means it's going to take me about 1700 years to replicate this. Are these calculations correct?
BlueMoon93
  • 906
  • 5
  • 16
4
votes
1 answer

Why multiplayer, imperfect information, trick-taking card games are hard for AI?

AI reached a super-human level in many complex games such as Chess, Go ,Texas hold’em Poker, Dota2 and StarCarft2. However it still did not reach this level in trick-taking card games. Why there is no super-human AI playing imperfect-information,…
Cohensius
  • 403
  • 3
  • 14
4
votes
0 answers

Given an input $x \in R^{1\times d}$ and a network with $s$ hidden layers, is the time complexity of the forward pass $O(d^{2}s)$?

I have a neural network that takes as an input a vector of $x \in R^{1\times d}$ with $s$ hidden layers and each layer has $d$ neurons (including the output layer). If I understand correctly the computational complexity of the forward pass of a…
Jonathan Azpur
  • 113
  • 3
4
votes
0 answers

When using hashing in tile coding, why are memory requirements reduced and there is only a little loss of performance?

In the book "Reinforcement Learning: An Introduction" (2018) Sutton and Barto explain, on page 221, a form of tile coding using hashing, to reduce memory consumption. I have two questions about that: How can this approach reduce memory consumption?…
F.M.F.
  • 311
  • 3
  • 7
3
votes
0 answers

Do we need as much information to know if we can can answer a question as we need to actually answer the question?

I am reading The Book of Why: The New Science of Cause and Effect by Judea Pearl, and in page 12 I see the following diagram. The box on the right side of box 5 "Can the query be answered?" is located before box 6 and box 9 which are the processes…
Lerner Zhang
  • 877
  • 1
  • 7
  • 19
3
votes
0 answers

How much time does it take to train DQN on Atari environment?

I am trying to build a DQN model for the Atari Pong game, but I am not sure whether the model is learning at all. I am using the architecture described in the paper Playing Atari with Deep Reinforcement Learning. And I tested the model on a simpler…
Ach113
  • 161
  • 5
3
votes
2 answers

Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?

I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is $\mathcal{O}(b^m)$. While I am reading, at some points, I found GBFS similar to DFS. It expands the whole branches…
iRestMyCaseYourHonor
  • 141
  • 1
  • 6
2
votes
1 answer

Why is exact inference in a Bayesian network both NP-hard and P-hard?

I should show that exact inference in a Bayesian network (BN) is NP-hard and P-hard by using a 3-SAT problem. So, I did formulate a 3-SAT problem by defining 3-CNF: $$(x_1 \lor x_2) \land (\neg x_3 \lor x_2) \land (x_3 \lor x_1)$$ I reduced it to…
xava
  • 423
  • 1
  • 3
  • 9
2
votes
0 answers

Is there a literature on the time complexity of Neural Networks?

There exist various blog posts describing the time complexity of Fully Connected Neural Networks (1, 2, 3, 4); Convolutional Neural Networks (CNN) (5) and of Long Short-Term Memory (LSTM) networks (6). However, this question seems to be absent in…
Daniel
  • 21
  • 4
2
votes
0 answers

Why do off-policy algorithms suffer from worse computational or time efficiency compared to on-policy algorithms?

When I run Soft-Actor-Critic (off-policy) in my Environment, the calculation of gradient updates takes almost twice the time compared to using PPO (on-policy). I also saw that ACER has a higher time complexity compared to PPO in this paper PPO with…
kitaird
  • 115
  • 5
2
votes
1 answer

How to know if a real-time classifier is achivable in a low-power emdedded system?

Say I have an Machine/Deep learning algorithm I developed on a desktop pc to achieve a real-time classification of time series events from a sensor. Once the algorithm is trained and performs good, I want to implement it on an low power embbeded…
Hattori
  • 201
  • 1
  • 7
2
votes
0 answers

What is symbol-to-number differentiation?

I recently came across symbol-to-symbol and symbol-to-number differentiation, out of which symbol to symbol seemed fairly straightforward - the computational graph is extended to include gradient calculations and relationships between gradients. I…
ashenoy
  • 1,409
  • 4
  • 18
1
2 3