# computational complexity

Computational complexity theory is a subfield of theoretical computer science that studies the resources required to solve computational problems and compares their practical difficulty.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## On the Computational Complexity of MapReduce

DevFeed: [On the Computational Complexity of MapReduce](<https://devfeed.tech/articles/on-the-computational-complexity-of-mapreduce-40368.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/10/05/on-the-computational-complexity-of-mapreduce/>)

Published: 2014-10-05T09:00:30Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [circuit-complexity](<https://devfeed.tech/tags/circuit-complexity.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [distributed-computing](<https://devfeed.tech/tags/distributed-computing.md>), [exponential-time-hypothesis](<https://devfeed.tech/tags/exponential-time-hypothesis.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [hierarchy](<https://devfeed.tech/tags/hierarchy.md>), [karloff](<https://devfeed.tech/tags/karloff.md>), [l-vs-p](<https://devfeed.tech/tags/l-vs-p.md>), [map-reduce](<https://devfeed.tech/tags/map-reduce.md>), [padding](<https://devfeed.tech/tags/padding.md>), [research](<https://devfeed.tech/tags/research.md>)

### AI overview

The article presents an accessible discussion of research analyzing the computational complexity of a theoretical model of the MapReduce framework. It describes open questions about MapReduce's power, including whether constant-round algorithms can determine graph connectivity and how the model relates to complexity classes such as P and L.

### Source excerpt

I recently wrapped up a fun paper with my coauthors Ben Fish, Adam Lelkes, Lev Reyzin, and Gyorgy Turan in which we analyzed the computational complexity of a model of the popular MapReduce framework. Check out the preprint on the arXiv. Update: this paper is now published in the proceedings of DISC2015. As usual I'll give a less formal discussion of the research here, and because the paper is a bit more technically involved than my previous work I'll be omitting some of the more pedantic details.

## How theoretical computer science explains the complexity of puzzle games

DevFeed: [How theoretical computer science explains the complexity of puzzle games](<https://devfeed.tech/articles/want-to-make-a-great-puzzle-game-get-inspired-by-theoretical-computer-science-40351.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/03/17/want-to-make-a-great-puzzle-game-get-inspired-by-theoretical-computer-science/>)

Published: 2014-03-17T10:00:55Z

Content type: opinion

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [computational complexity](<https://devfeed.tech/topics/computational-complexity.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Computer science](<https://devfeed.tech/topics/computer-science.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Mazes](<https://devfeed.tech/topics/maze.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [art-gallery-problem](<https://devfeed.tech/tags/art-gallery-problem.md>), [bin-packing](<https://devfeed.tech/tags/bin-packing.md>), [board-games](<https://devfeed.tech/tags/board-games.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [computer](<https://devfeed.tech/tags/computer.md>), [computer-science](<https://devfeed.tech/tags/computer-science.md>), [exp](<https://devfeed.tech/tags/exp.md>), [game](<https://devfeed.tech/tags/game.md>), [games](<https://devfeed.tech/tags/games.md>), [games-on-graphs](<https://devfeed.tech/tags/games-on-graphs.md>), [graph-coloring](<https://devfeed.tech/tags/graph-coloring.md>), [greedy-spiders](<https://devfeed.tech/tags/greedy-spiders.md>), [mario](<https://devfeed.tech/tags/mario.md>), [nintendo](<https://devfeed.tech/tags/nintendo.md>), [np](<https://devfeed.tech/tags/np.md>), [np-completeness](<https://devfeed.tech/tags/np-completeness.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [pancake-flipping](<https://devfeed.tech/tags/pancake-flipping.md>), [pspace](<https://devfeed.tech/tags/pspace.md>), [puzzle](<https://devfeed.tech/tags/puzzle.md>), [science](<https://devfeed.tech/tags/science.md>), [starcraft](<https://devfeed.tech/tags/starcraft.md>), [video-games](<https://devfeed.tech/tags/video-games.md>)

### AI overview

The article explains that NP-hardness in games describes worst-case computational complexity, not how difficult a game is for human players. It uses examples including Pokémon, Super Mario Bros., Candy Crush Saga, Pac-Man, Doom, Starcraft, Tetris, chess, checkers, and Go to discuss hardness results and practical algorithms.

### Source excerpt

Two years ago, Erik Demaine and three other researchers published a fun paper to the arXiv proving that most incarnations of classic nintendo games are NP-hard. This includes almost every Super Mario Brothers, Donkey Kong, and Pokemon title. Back then I wrote a blog post summarizing the technical aspects of their work, and even gave a talk on it to a room full of curious undergraduate math majors. But while bad tech-writers tend to interpret NP-hard as "really really hard," the truth is more complicated.