In terms of "computational complexity" we mean the following:

Consider the following generalization of Sudoku. There is a number, N, and a grid of squares with N^2^ squares per side. (So the grid in total has N^4^ squares.) Each row and column of the grid has N^2^ squares. The grid therefore contains an N^2^ number of NxN subgrids (this corresponds to the 3x3 boxes in regular sudoku, called Houses). The puzzle is to fill each row, column, and house with the numbers from 1 to N^2^ with no duplicates.

The complexity is then a measure of how much harder the puzzles get when N is increased. Sudoku is a classic example of a so-called "NP-Hard" problem. Most puzzles that people think of as difficult are NP-hard. The ELI5 is that given a claimed solution to a sudoku puzzle, you can check if it really is the solution quickly (where again "quickly" is in terms of N). This is not true for the hardest types of puzzles in the witness.

This is only a proxy for how difficult humans will find the smaller puzzles but it's remarkably accurate. The hardest puzzles using every mechanic from the witness (realistically, only using two of them including the last one) are going to be much harder for a human than the hardest sudokus.