  Why should moral philosophers, moral psychologists, and machine ethicists
care about computational complexity? Debates on whether artificial intelligence
(AI) can or should be used to solve problems in ethical domains have mainly
been driven by what AI can or cannot do in terms of human capacities. In this
paper, we tackle the problem from the other end by exploring what kind of moral
machines are possible based on what computational systems can or cannot do. To
do so, we analyze normative ethics through the lens of computational
complexity. First, we introduce computational complexity for the uninitiated
reader and discuss how the complexity of ethical problems can be framed within
Marr's three levels of analysis. We then study a range of ethical problems
based on consequentialism, deontology, and virtue ethics, with the aim of
elucidating the complexity associated with the problems themselves (e.g., due
to combinatorics, uncertainty, strategic dynamics), the computational methods
employed (e.g., probability, logic, learning), and the available resources
(e.g., time, knowledge, learning). The results indicate that most problems the
normative frameworks pose lead to tractability issues in every category
analyzed. Our investigation also provides several insights about the
computational nature of normative ethics, including the differences between
rule- and outcome-based moral strategies, and the implementation-variance with
regard to moral resources. We then discuss the consequences complexity results
have for the prospect of moral machines in virtue of the trade-off between
optimality and efficiency. Finally, we elucidate how computational complexity
can be used to inform both philosophical and cognitive-psychological research
on human morality by advancing the Moral Tractability Thesis (MTT).
