Determinism vs Nondeterminism

Image description: Sudoku, easy to verify, hard to solve.

Determinism vs Nondeterminism

The P vs NP problem

There is a classic and important problem in computer science called the “P versus NP problem.” As an aspiring developer and former math teacher, I was intrigued by the problem and specifically the terminology. First, let me try to explain the problem.

• P stands for a problem that can be solved in a reasonable time by a computer (Polynomial time).

• NP stands for a problem that can be verified in a reasonable time but not solved in a reasonable time (Nondeterministic Polynomial time).

For example, a sudoku puzzle can be verified quickly and deterministically. That is, if you want to check if a solution is correct, you can follow a given algorithm that will always take the same amount of time and will always give you the same answer (for the same puzzle).

To solve the puzzle, though, you must either use a nondeterministic approach and try different methods depending on your own hunches and feelings, or be prepared to spend a very, very long time trying to come up with a deterministic algorithm, that is identical for all sudokus, and then following it.

Why this matters

The question of the problem is whether P = NP. That is, if we can find a quick way to verify a solution to the problem, does that then mean that there is a quick way to solve the problem? The question is, as of now, unanswered, and if it were to be answered and found that P = NP, global chaos would likely follow.

“Imagine that hackers could find your password as quickly as they could verify that it was correct. Not good.”

Most modern cryptography relies on the fact that it is harder to find a solution than to verify it.

Another interesting aspect of the problem is that if you solve one special case of the problem (for example, the sudoku problem), you solve all cases of the problem. So if you are an agent of chaos, and, like the Joker of Batman, would like to see the world burn; make sure to spend some time on trying to solve this!

Clarifying Determinism vs Nondeterminism

• Determinism: If the starting conditions are the same, the outcome will always be the same.

• Nondeterminism: The possibility of different outcomes even though starting conditions remain the same.

In computer science the cause is often randomness; in other contexts the cause may be ascribed to free will.

From philosophy to system integration

Determinism vs. Nondeterminism is (and has been) a hot topic in fields ranging from physics to philosophy, but the reason I am bringing it up is actually the field of System Integration.

It seems like a no-brainer that integration flows should always be deterministic; that is, if you input A and get output B, you should always get output B when you input A.

Where Nondeterminism fits in system integration

Well, believe it or not, there is room for nondeterminism even in integration, where you generally expect predictable results.

How, you ask? Join us at our Agent in a Day workshop at Contica on October 22 at 16:00 on Masthamnsgatan 1, and we will try to convince you that this is the case.

You might even find out that your current business processes might be more nondeterministic than you think. And that getting more control over that nondeterminism is a good thing.

Register here for the event – Only 50 slots available!

Footnote

The “P vs NP problem” is a complex and nuanced problem and I had to do some simplification to avoid being too verbose here. If you want to discuss the problem further or want to know more about the event, make sure to reach out!