G12FCO -- Formal Computation

Lecture 13 -- Beyond NP-completeness

Other areas of NP-completeness

• Map colouring -- how many colours do you need to colour a map so that no two adjacent countries are the same colour? [And yes, I know about the 4-colour theorem.]
• Three-sex marriages. If you have groups of males and females, and know which ones are compatible, then you can feasibly marry them off, for various definitions of `compatible' and `marry'. But if you have males, females and aliens, then the problem is NP-complete. Luckily, this only matters to X-Files, not to the human race.
• Timetabling. This is in P if staff and students are `always available', but if you allow people to refuse to lecture at particular times, it becomes NP-complete.
• Doing jigsaw puzzles. You have to imagine that there is lots of sky, and lots of pieces that sufficiently nearly fit that it's only much later that you realise that you've gone wrong.
• Various games. These are typically NP-complete or NP-hard (and PSPACE-complete). An example is Geography, where you have to take turns to name towns that begin with the letter that the previous town ended with. [In the UK, Halifax is a killer, so Norwich, Edinburgh, etc. are blunders.]
• Longest common subsequence, and various other similar problems of interest in genetics [DNA matching]. Exact matching of contiguous sequences is in P, but you're in trouble as soon as you allow gaps or ambiguities or mistakes or `wild cards'.
• Parsing context-free grammars [excuse the jargon!]. If you want a program to be able to understand a language, you have to design the language pretty carefully. Most real languages are simply written down without too much thought, but luckily their inventors have usually just re-designed the language as soon as it proves difficult to parse.
• Program optimisation. It's not too hard to produce some sort of machine code that runs on a computer to give effect to a program [in a well-designed language!], but you're in difficulties if you need to do it in limited amounts of space or with limited numbers of `registers' or in various other ways that imply a deeper knowledge of the program.
• Zillions of others -- see Garey and Johnson to get a flavour.

`My problem is NP-complete -- does that mean I can't solve it?'

1. There may be lots of instances that are tractable. Most numbers are easily proved to be prime or composite. VC is in P if the number of forts is bounded [even if the number of roads isn't]. Timetabling, even with forbidden periods, is nearly always solvable by `branch and bound' techniques in a reasonable time, it's just that a tiny fraction of cases need repeated backtrackings; likewise with many packing and optimisation problems. [Usually you know how many suitcases you need for your luggage!]
2. There may be approximate solutions that are in P, and the difficulty is in squeezing the last drop of efficiency. For example, by starting with a minimal spanning tree and then using local optimisations, it is usually possible to do well with instances of TS. Indeed, this usually works very well, and it is guaranteed to work quite well.
3. There may be a pseudo-polynomial-time algorithm for the problem. This means that the algorithm is polynomial in the size of the input and the largest number involved [not the number of digits of that number]. This is true but unhelpful for factorisation; but there are many packing and scheduling problems where it's true and helpful, in other words where the intractable cases are difficult only because the numbers involved are huge [with millions of digits], and the more normal cases with human-scale numbers are tractable. The NP-complete problems are thus divided into pseudo-NP-complete and strongly-NP-complete problems [which remain NP-complete even if only small numbers are involved].
4. There is also the parallel universe of co-NP problems [which are solvable in polynomial time if you are lucky with a guess and the answer is `no']. It is unknown whether co-NP = NP. Since co-P = P, co-NP /= NP => P /= NP [but not the converse]. If co-NP /= NP [as we expect], then there is quite a lot of known structure in the universe of problems. Firstly, there is then a countably infinite hierarchy of problems that are harder than P but are within co-NP U NP. Then there is another countably infinite hierarchy of problems that are in NP but not co-NP but are not NP-complete. Then there are the pseudo-NP-complete problems, and the strongly-NP-complete problems. Then there is the parallel universe of problems in co-NP but not NP, building up to strongly-co-NP-complete. Even then, there are a whole pile of `resolution theorems', which demonstrate hierarchies within hierarchies. All of this is well beyond the scope of this module; and there is more to come, see below.

Nevertheless, it remains the case that many NP-complete [and other P-hard] problems seem to be difficult to get a good handle on. At least you have the consolation that all NP-complete problems stand or fall together, that many of them have attracted a great deal of attention from very clever people, and that none of them could solve your problem efficiently either. If NP /= P, then there is no efficient way to solve your problem, except by having the luck to guess a solution. If, against expectations, it turns out that NP = P, then we will know that there is a polynomial-time solution to your problem, and it is extremely likely that the proof will show us some way to construct it. Indeed, there is a construction rather similar to Cook's theorem which generates a polynomial-time algorithm for any problem in P, but the construction is intractable!

If NP = P, then almost all problems in P are P-complete. The reason is, basically, that in polynomial time we can solve the problem, hence decide whether the decision should be yes or no, hence map onto a suitable instance of almost any other problem. In such a circumstance, the whole concept becomes meaningless.

Beyond NP-completeness?

Firstly, we could change the `hardware'. We haven't yet explored what we mean by a computer [to come later in the module!], but we have vaguely assumed that it carries out some bounded number of steps per second. If we want to make intractable problems tractable, then we have to find ways of carrying out more and more steps. Two of these ways are of particular interest: parallel processing and quantum computation.

Parallel processing with a fixed number of processors, or even with a polynomially-bounded number of processors, is not really any advance on normal computation [not as far as the theory goes, though of course it could make real life a whole lot faster]. But an exponentially-growing number of processors -- that would help! For example, suppose the processors could replicate themselves at will. Then solving [generalised] chess becomes an O(N) problem. The idea is that at each position in the analysis, you spawn off a new processor for each possible move, set them running, and collate their results. The time taken is bounded by the depth of the search, not by the number of positions looked at. There has been recent interest in `genetic' computers. where a beaker of DNA is set to compute something within its sequence; if the DNA could replicate itself during the experiment, we might get somewhere [at the possible expense of filling the entire universe with solid DNA!].

Quantum mechanics appears to offer another way out. In some sense, quantised particles evolve over all possible randomised outcomes of their experiments in parallel, until the observer measures the result. The idea would be that you set up a suitable particle, primed into a quantum-mechanical state which represents, say, a network. You then carry out an experiment which represents, say, the HC decision problem, and observe in such a way that only the `lucky guesses' survive; the particle tries all guesses in parallel, and the measurement of the outcome tells you what the decision is. Pretty esoteric stuff! But the Universe manages to compute fast enough to evolve the entire universe exactly in real time. How does it do that?

Secondly, we can ask different problems. For example, instead of decisions, we can ask for counts or values: `How many Hamiltonian circuits ...?', `What is the shortest Travelling Salesman route ...?', etc. These are called enumeration problems, with their own feasibility classes such an #P [`number-P']. Clearly, an enumeration problem is at least as hard as the corresponding decision problem. Quite often, as with TS, the decision problem can be used to solve the enumeration problem and there is no real difference. But also quite often the enumeration problem is significantly harder [if NP /= P]. For example, the `matching problem' [2-sex marriages] is in P, but counting the matchings is #P-complete. You can also re-work the previous `worst-case' analysis for `average-cases'.

Thirdly, we can put different constraints on the problems, asking about polynomial space [PSPACE], exponential time [EXP] or space, logarithmic time or space, each with its non-deterministic, complete, hard and co- versions [e.g. the class of `co-NPSPACE-hard' problems]. It's a jungle out there! Garey and Johnson, Papadimitriou and Harel all have lots of diagrams showing some of the inclusion relationships between these classes of problems.

top of page

G12FCO home page

Previous lecture

Next lecture

Problem Class 4