Los acertijos de lápiz y papel han captado el interés de la comunidad científica en los últimos años, especialmente los inventados y popularizados por la editorial japonesa Nikoli. La razón de este interés radica en la dificultad inherente para resolver estos acertijos, lo que ha llevado a muchos estudios sobre su complejidad computacional. Se ha demostrado que varios acertijos de Nikoli son NP-completos, y se ha observado una tendencia decreciente consistente antes para el tiempo transcurrido entre la publicación de un nuevo acertijo de Nikoli y el establecimiento del primer resultado de dureza del acertijo (desde intervalos de casi 20 años para la mayoría de los acertijos más antiguos de la compañía hasta intervalos de menos de 5 años para la mayoría de los más nuevos). En este documento, demostramos que Nagenawa, un acertijo de Nikoli, es NP-completo.
Bordin et al. (Thu,) estudiaron esta cuestión.