2
$\begingroup$

This is a Masyu puzzle with its solution on the right

The puzzle is made up of (n x n) squares so when taking the problem the input size would be n.

Rules of Masyu:

  • The goal is to draw a single continuous non-intersecting loop that properly passes through all circled cells. The loop must "enter" each cell it passes through from the center of one of its four sides and "exit" from a different side; all turns are therefore 90 degrees.
  • White circles must be travelled straight through, but the loop must turn in the previous and/or next cell in its path.
  • Black circles must be turned upon, but the loop must travel straight through the next and previous cells in its path.
$\endgroup$
7
$\begingroup$

Because a problem is in NP if, and only if, "yes" instances have succinct certificates. Informally, this means that the solution to any instance is at most polynomially large in the size of the instance, and if you're given an instance and something that is claimed to be a solution to it, you can check in polynomial time that it really is a solution.

More formally, a language $L\subseteq\Sigma^*$ is in NP if, and only if, there is a relation $R\subseteq \Sigma^*\times\Sigma^*$ such that:

  1. there is a polynomial $p$ such that, for all $(x,y)\in R$, $|y|\leq p(|x|)$;
  2. the problem of determining whether $(x,y)\in R$ is in P;
  3. $L = \{x\mid \exists y\,(x,y)\in R\}$.

For example, consider graph 3-colourability. You can describe a graph on $n$ vertices just by writing out its adjacency matrix, which requires $n^2$ bits. If a graph is 3-colourable, you can describe a colouring in $2n$ bits: just list the colour of each vertex in turn (say, $00$ for red, $01$ for green, $10$ for blue). So, if a string $x$ describes a graph, and that graph is 3-colourable, each 3-colouring can be described in a string $y$ with length $2\sqrt{|x|}\leq 2|x|$. Furthermore, if I give you a decription of a graph and a description of a 3-colouring, you can easily check in polynomial time that it really is a 3-colouring: just check that adjacent vertices always have different colours. So, the relation $$\{(x,y)\mid x\text{ describes a graph $G$ and $y$ describes a 3-colouring of }G\}$$ proves that 3-colourability is in NP.

So, to show that Masyu is in NP, we just need to construct the corresponding relation $R$. We can describe an $n\times n$ instance of Masyu in $2n^2$ bits: for each square in turn, write $00$ if it's blank, $01$ if it contains a black circle and $10$ if it's a white circle. We can describe a solution in $3n^2$ bits: for each square in turn, write $000$ if the square isn't on the solution path, and $100$, $101$, $110$ and $111$ if it's on the path and the next square is the one to the right, left, up and down, respectively. It's easy to check in polynomial time that a claimed solution really is a solution: just find a square that's on the path, follow the path and check it satisfies the criteria.

$\endgroup$
  • $\begingroup$ We can also "describe an $n\hspace{-0.03 in}\times \hspace{-0.03 in}n$ instance of Maysu" with C circles in $\: \lceil \hspace{.02 in}\log_{\hspace{.03 in}2}(C\hspace{-0.04 in}+\hspace{-0.06 in}1)\rceil+(2\hspace{-0.04 in}\cdot \hspace{-0.05 in}\lceil \hspace{.02 in}\log_{\hspace{.03 in}2}(n)\rceil \hspace{-0.05 in}\cdot \hspace{-0.04 in}C\hspace{.03 in}) \:$ bits, so your proof only works when $n$ is given in unary. ​ ​ ​ ​ See this question. ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Feb 6 '16 at 16:05

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.