Design considerations for P and NP

Zoe Rose
Zoe Rose
Jan 5, 2017 · 5 min read

There are lots of different kinds of problems in the world. Some problems have a very specific attribute: they have only one correct answer.

Problems with only one correct answer come in two types:

A) P

B) NP

Oh no! It’s MATHS. Don’t worry, the experience design bit is coming soon.

P problems

These are problems where you can estimate how long it will take to solve the problem in advance. For example: imagine if you want to find out how many people with the first initial ‘J’ there are in an old-fashioned phone book. You can solve this problem by:

1. Opening the phone book

2. Looking at the first entry

3. Seeing if the person listed has the first initial ‘J’

4. Recording a ‘yes’ if they do and ‘no’ if they don’t

5. Moving to the next line and repeating the process.

You could repeat this process indefinitely — for the entire phone book, in fact. The repeatability makes this little sequence an algorithm.

By looking at how thick the phone book is, you can make a good guess how long it will take to go through.

At any stage in the process, you can see how much of the phone book is left, and know how much longer it is likely to take.

That is the essence of a P problem: you can guess how long it will take to solve.

NP problems

NP is different.

Solving an NP problem is like doing a maze, but a maze where every time you hit a dead end you go back to the start again. There is no method, no technique, no clever tactic that can speed the solution up. There is also no way of knowing how close a solution is — the solution might be revealed on your next attempt, or it might be a hundred, a thousand, maybe a billion attempts away.

With an NP problem, you can’t guess how long it is going to take, so you can’t predict if you’ll get the answer in a reasonable time — whatever ‘reasonable’ means in your context. There’s no clever little algorithm that can help you to guess, you have to rely on brute force.

You also need luck: there’s no guarantee in NP that there is a correct answer to be found. We can thank Alan Turing for this bit — he found that it’s impossible to determine whether an algorithm will run forever on some problems or not.

P, NP, time and effort

If you’ve followed this so far — congratulations! You now understand the foundations of cryptography (which is, as far as we know, NP.) (If you fancy a go, there’s a million pound prize for anyone who can demonstrate that P=NP.)

At this point, the Maths starts veering into polynomial time (NP stands for non-deterministic polynomial time) and I confess, my capacity to get my head around the whole thing runs out. The key, though, is how long it will take — which is not measured in minutes, but in the number of elements that the algorithm has to manipulate (more here).

So P and NP problems are fundamentally differentiated through effort.

On to the design considerations!

And now, a wild oversimplification:

In the world of web services, there is a spectrum between two extremes:

A) goal-oriented services

B) not-goal-oriented services

Websites that are fundamentally not goal-oriented of the kind that thrive on clicks: Pinterest, Twitter, Buzzfeed. You can noodle around on them for ever, explicitly because you’re not really trying to achieve anything specific.

In the middle of the spectrum, services like Asos: where users often find themselves noodling around for fun, but will hopefully purchase a skirt as well.

The goal-oriented websites, though, have an interesting attribute: if we tweak our definition very slightly from “only one correct result” to “only one result that the user accepts”, we see that task oriented websites can be seen (if you squint) through the lens P and NP.

P-ish tasks

- Buying groceries on a supermarket app

- Finding a hammer on eBay

- Checking what’s on at the movies

In each instance, there are a finite set of options, the user chooses one (or several in the case of the groceries), and having chosen, completes the task. A user who visits eBay does so with confidence that, within a few minutes of scrolling, they’ll have found acceptable hammer. The movie-goer will look at each of the movies on offer, and either decide to go to one or not.

NP-ish tasks:

- Dating

- House hunting

- Job hunting

For each of these goals, the user has a specific thing they want to achieve, but no way of knowing how long it will take — your next boyfriend could be on the next page of eharmony results, or you might not find him for weeks. He might not be on eharmony at all, you just don’t know. Maybe you’ll just stay single forever.

But if you do find a new boyfriend, though, you’ve met your goal — and you will stop using the site.

Finding a new place to live, or a new job, come with the same issue — maybe it will be today, maybe tomorrow, maybe never. You just don’t know.

The emotional range of NP

Solving NP problems is inherently, profoundly emotional — it’s complex, difficult, tiring, and there are many options to weigh up.

Some considerations:

  • As time passes, users with NP problems can move from high hopes and expectations to grinding repetition and despair — all while using the same interface. Perky, ‘delightful’ features could become grating if not actively insulting. What appeals to a new user might drive away a user who has been returning daily for months away.
  • It’s reasonable to expect than a substantial number of users approaching an NP task have just had something in their lives go wrong — a breakup, an eviction, a job gone sour. Sensitive copy should offer hope without promises — any promises that a solution is imminent will ring hollow to a long-term user.
  • Completion bars should be used judiciously or not at all, if they imply that the end-goal could be near.
  • For goal-driven users with acute problems, the user’s hope will often be to use the site for as little time as possible — metrics such as bounce-rates and page views should be treated judiciously, as they could be showing success rather than failure.
  • Some users with particularly acute problems won’t necessarily want to acknowledge they have an acute problem — copy that allows a user to maintain an internal narrative that they’re in control of their situation could contribute to a smoother emotional experience.
  • Along with goal-driven users, there are likely to be more speculative users — people who might not have a problem at all, and are doing exploratory or opportunistic discovery work. These users are far less likely to convert (whatever conversion means in the context of the service), but could become goal-driven at a later date, so features that encourage exploration could be valuable as long as they don’t detract from the goal-oriented users achieving their goal.

Zoe Rose

Written by

Zoe Rose

IA, UX, education. Five-year-old wrangler. British/Australian. General enthusiast.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade