When considering how multi-thread-friendly our program must be, my team puzzled about whether there's anything that absolutely cannot be done on a single-core CPU. I posited that graphics processing requires massively parallel processing, but they argue that things like DOOM were done on single-core CPUs without GPUs.
Is there anything that must be done on a multi-core processor?
Assume there is infinite time for both development and running.
If you don't care about the running time, anything you can do on a multi-core machine, you can do on a single-core machine. A multi-core machine is just a way of speeding up some kinds of computations.
If you can solve a problem in time $T$ on a multi-core machine with $n$ cores, then you can solve it time $\sim Tn$ (or less look at Amdahl's law) on a single-core machine. The single-core machine can emulate a multi-core machine using time-slicing / time-sharing.
The question is: under what constraints?
There are certainly problems where, if we ask the question "can we solve this problem on hardware X in the given amount of time", the answer will be no.
But this is not a "future-proof" answer: things which in the past could not be done fast enough in a single core probably can be now, and we can't predict what future hardware will be capable of.
In terms of computability, we know that a single-tape Turing Machine is capable of computing all the same functions as a single or multi-core computer, so, runtime aside, there are no problems that a multi-core computer can solve that a single-core can't.
In terms of something like graphics, literally everything that is on the GPU could be done on the CPU... if you are willing to wait long enough.
As other answers have pointed out, a single CPU can always emulate multiple CPUs by slicing time and playing the role of each virtual CPU. This emulation will certainly calculate the correct answers.
In the real world, execution time may be important. It could mean the difference between a mediocre frame rate and a stellar visual experience. Or the difference between profit and loss in trading.
One pathological situation where a multiprocessor is vastly faster than a uniprocessor is where the processing is a data pipeline, context switching is expensive, and the machine code for each pipeline stage just barely fits in a CPU's cache.
Let me illustrate with some numbers. Suppose you have a data pipeline (3D rendering, etc.) that has 4 processing stages, each stage has 256 KiB of program code, and you conveniently have 4 CPUs with 256 KiB of L2 cache. If you try to run this processing on a single CPU, then switching between the 4 tasks will be expensive and involve heavy cache misses. On the other hand if you run it on a 4-core system, the calculation could potentially be very smooth, cache misses are minimal, and context switches are non-existent. (As a side note, this is related to the notion of pinning certain applications to certain cores - e.g. only doing OS kernel operations in one core, or TCP/IP handling, etc.)
It's much harder to develop really nefarious data races with a single CPU. I mean, sure, you can pull off tearing between words if you interrupt a single CPU, but can you build exotic scenarios where there is no single interleaving of threads which does what you want?
Okay, maybe making insidious bugs doesn't count as a valid use of multi-code advancements. As it turns out, there's not much that mutli-core can do that single core cannot given time. The reason is simple. If you try to avoid those evil data races, you have to have synchronization points in your code. If you model your code as a lattice of computations where ones inputs must be complete and synchronized before you can calculate and produce outputs, it's easy to see that a single CPU can simply work their way along the lattice, calculating the next available block of work.
In fact, if you can demonstrate that your algorithm can be solved by a Turing machine (which is virtually every algorithm we care about), it can be proven that the algorithm can be done by not only a single core CPU, but in fact a state machine with a very long piece of tape for memory!
The CHESS race detector actually leverages this to find race cases. It runs everything singlethreaded and systematically explores all possible interleaves between threads, trying to find cases where a test fails because of a race case. CHESS depends on the fact that you can run any multithreaded application on a single core.
The cases where you need multicore appear when you start stretching the limits of hardware. The obvious one is when you have time constraints. Some problems with realtime time constraints are impossible to do single core because they simply can't drive a single core's clock fast enough. There's a reason CPUs climbed up to 4Ghz and then settled down a bit, preferring more cores at lower speeds.
A more exotic version of this timing constraint is in hard-real time systems. In some hard real time systems, the service of interrupts is so demanding that you actually have to pick a multi-core CPU that lets you divvy the interrupts up across the cores, or you run into timing limitations.
Another limit arises with data busses. Consider the Blue Gene/P as an example. JUGENE, a particular Blue Gene/P supercomputer, has 144 terabytes of memory. They simply don't make single CPU computers that can access all of that memory.
If you need to observe a process running on a single processing element without disturbing its real-time behavior (or as little as possible), like for benchmarking or activity logging, you'll probably need a separate processing resource.
The other answers adhere to the limited view of parallelism as "distributed concurrency". This gives some answers: in a clean model of computation à la Turing, multiple cores do not offer an advantage; the only advantage you may get is efficiency.
There is the one thing multiple processing units (PUs) can do that a single one can not, though: execute operations in parallel, that is at the same time.
That is very useful if you run multiple programs at the same time. Granted, it is only rarely that you absolutely need more than concurrent execution, and most uses come down to increased efficiency. But there is this difference.
Say you need to process data sensor data from multiple sources in real time. Whatever that means precisely in your application, one PU can only handle so many input streams concurrently without violating its response time limit. So you need multiple PUs once you have too many sensors for your current PU generation.
In the more classical realm, one maybe convincing example are portfolio algorithms. Say you have a problem for which you have multiple (say $k$) algorithms with orthogonal costs; good cases of one are bad cases for others. You can not quickly tell which one is best for a given input, though.
You can run all algorithms in parallel and abort once one finishes. If you have at least $k$ PUs, you get the minimum running time among all $k$ algorithms in the portfolio. With only one PU, you'd get $k$ times that, assuming a fair scheduler, plus all the overhead.
from a CS pov, "multicore" is not that much different in theory than "distributed computing". the basic concept is "independent computing elements (that compute in parallel". so slightly rephrasing the question ("multicore" is not really exactly a theoretical concept in CS) leads to some other possibilities. as pointed out in other answers, sequential programming is equivalent to parallel programming from a CS pov. this goes back to the definition of the theoretical system for computing, namely a Turing machine. theoretical analysis of CS performance is ultimately in terms of TMs where the distinction of parallel vs sequential does not really apply (although there is some rough analogy with multitape TMs).
but considering this question less abstractly, distributed computing is indeed superior or possibly nearly even required for some problems involving fault tolerance. in this area there is a concept that it applies when/ where the independent computing elements are taken to have some degree of unreliability (this is not really a universally applicable assumption for all contexts). here are several cases where fault tolerance is improved with or even requires independent computing elements.
consider that each processor has an independent "[x]%" chance of failing during computation. a system can be devised whereby through communication the overall fault tolerance of the system is superior to individual components. this was applied many decades ago eg in Space Shuttle systems. more recently there are basic protocols designed to utilize it eg Paxos which solve the so-called consensus problem. a more down-to-earth example is Google which has a lot of proprietary algorithms to essentially build their supercomputer(s) out of individually unreliable elements coupled with fault-tolerant algorithms.
Bitcoin involves distributed transactions to compute the ledger and that is not merely due to sheer processing load issues. the algorithm is carefully designed to thwart corrupt nodes. in short it "solves"/ implements the Byzantine generals problem which is not merely about maximizing parallel performance, it involves independent entities "checking" each other and "algorithmically/ cryptographically/ securely" rejecting invalid computations aka a sort of "cheating" or "corruption".
a classic analysis of parallelism concludes there are about 7 "fundamental" problem pattern types that decompose into particular parallel execution breakdowns. see The Landscape of Parallel Computing Research: A View from Berkeley
there is some element of an open theoretical question here wrt performance considerations addressed in most other answers. the question of whether there are any problems that are "inherently faster" in parallel than sequential is also known roughly as the P=?NC problem where NC is considered the class of "efficiently parallelizable" algorithms and P is "efficient [sequential] algorithms"
