0
$\begingroup$

We know an $n$-Sudoku puzzle is with $n \times n$ subgrids consisting of $n \times n$ cells; you will fill it with numbers from $1$ to $n^2$.

Candidate solution have size polynomial in $n$, and can be checked in a time polynomial in $n$. The number of cells filled in each solution is at most $n^2 \times n^2 = n^4$. The length of each number is $\log(n^2) = 2\log n$. So the length of each solution is $O(n^4\log n)$, which is $O(\leq n^5)$, since $\log n \leq n$. (The reason is that $2^n \geq 1 + n$ by the binomial theorem, so $2^n \geq n$, and we then take $\log_2$ of both sides.)

My only question is why the number of each number is $\log(n^2)$.

$\endgroup$
0
$\begingroup$

My only question is why the number of each number is $\log(n^2)$.

We need at most $\lceil \log_2 N\rceil+1$ binary digits in order to present a natural number $N$ in a binary system.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.