What computational complexity classification does autonomous/self-driving cars belong to? Self-driving car technology continues to attract popular attention and interest in today's media, but how would a computer scientist explain the theoretical nature of the problem? For example, we are frequently told that Sudoku and Go are examples of NP-completeness and PSPACE-completeness, and a range of practical progress has been made in dealing with these two categories. So similarly with autonomous vehicles, I think laypeople people (like myself) intuitively accept that learning to drive properly is a &quot;problem&quot;, but then, what is the underlying problem that such machine learning algorithms are trying to tackle?
I did some Googling around and found different articles and papers alluding to some parts or formal abstractions of the driving problem and/or maybe robotics being PSPACE-complete. So is that the answer basically? Or is it that the question is too vague to be answerable? Or even that there hasn't been a clear understanding yet, because the area is fairly new? I'm just really curious, but didn't find anything explaining this at a high level. But when I took CS in college, the professors would emphasize to programmers that understanding the nature of the problem can be very important, e.g. understanding if your specific problem is in P or is NP-complete, and so forth.
Complexity theory is mostly interested in decision problems and in optimization problems, and your problem belongs to neither class. Complexity theory is also interested in other resources, such as communication, but at the cost of neglecting computational complexity.
Apart from not fitting the mold of problems typically considered in complexity theory, your problem is also not well-defined. There is no accurate and formal specification of the required behavior. Without such a specification it is hard to mathematically gauge its complexity.
While it is possible to abstract some aspects of &quot;autonomous driving&quot; into pieces which do fit current theory, in my opinion it doesn't bring us any closer to understanding the actual difficulty of solving this problem.
Complexity theory won't help you in understanding the problem of poverty, or even the problem of writing poetry, or even the decision problem of determining whether a given poem is &quot;good&quot; or &quot;bad&quot;. It is not an all-encompassing theory of reality, and as you observe, it doesn't even capture all problems in which computers are involved.
Autonomous driving, in particular, combines hardware, software, legal issues, and philosophical issues. When designing autonomous vehicles, we also design the sensors available to the software controller, the mechanical interventions it is allowed to use, the laws it complies with, and so on. All of these important and pertinent issues are beyond what computational complexity theory offers.