# On the Computational Complexity of Ethics: Moral Tractability for Minds and Machines

arXiv: https://arxiv.org/abs/2302.04218 · HTML: https://mlsanity.com/paper/2302.04218/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 185 references that are in the map.
- First posted on arXiv 8 Feb 2023.

## Builds on (most cited first, 16 of 16)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Artificial Intelligence, Values and Alignment](https://mlsanity.com/paper/2001.09768/) (2020)
- [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Self-Driving Cars: A Survey](https://mlsanity.com/paper/1901.04407/) (2019)
- [Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems](https://mlsanity.com/paper/1709.08071/) (2017)
- [A Theory of Consciousness from a Theoretical Computer Science Perspective: Insights from the Conscious Turing Machine](https://mlsanity.com/paper/2107.13704/) (2021)
- [From average case complexity to improper learning complexity](https://mlsanity.com/paper/1311.2272/) (2013)
- [Implementations in Machine Ethics: A Survey](https://mlsanity.com/paper/2001.07573/) (2020)
- [The no-free-lunch theorems of supervised learning](https://mlsanity.com/paper/2202.04513/) (2022)
- [What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives](https://mlsanity.com/paper/1309.2802/) (2013)
- [Monte Carlo Sampling Methods for Approximating Interactive POMDPs](https://mlsanity.com/paper/1401.3455/) (2014)
- [On Automating the Doctrine of Double Effect](https://mlsanity.com/paper/1703.08922/) (2017)
- [Toward the Engineering of Virtuous Machines](https://mlsanity.com/paper/1812.03868/) (2018)
- [Artificial virtuous agents in a multiagent tragedy of the commons](https://mlsanity.com/paper/2210.02769/) (2022)
- [Coordination Complexity: Small Information Coordinating Large Populations](https://mlsanity.com/paper/1508.03735/) (2015)

## Built on by (most cited first, 2 of 2)

- [The Universal Landscape of Human Reasoning](https://mlsanity.com/paper/2510.21623/) (2025)
- [Accounting for Context: Shaping Moral Credences for Value Alignment](https://mlsanity.com/paper/2606.06972/) (2026)

## Abstract (arXiv)

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).