Choco Banana is NP-Complete∗

被引：0
|
作者：
Iwamoto, Chuzo [1 ]
Tokunaga, Takeru [2 ]
机构：
[1] Hiroshima Univ, Grad Sch Adv Sci & Engn, Higashihiroshima 7398521, Japan
[2] Hiroshima Univ, Sch Informat & Data Sci, 739-8527, Higashihiroshimashi 7398527, Japan
来源：
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2024年 / E107A卷 / 09期
关键词：
Choco Banana; pencil puzzle; NP-complete;
D O I：
10.1587/transfun.2023DML0001
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Choco Banana is one of Nikoli's pencil puzzles. We study the computational complexity of Choco Banana. It is shown that deciding whether a given instance of the Choco Banana puzzle has a solution is NP-complete.
引用
收藏
页码：1488 / 1491
页数：4
相关论文
共 50 条
  • [21] Broadcasting with the least energy is an NP-complete problem
    Yang, Wuu
    Tseng, Huei-Ru
    Jan, Rong-Hong
    Shen, Bor-Yeh
    MUE: 2008 INTERNATIONAL CONFERENCE ON MULTIMEDIA AND UBIQUITOUS ENGINEERING, PROCEEDINGS, 2008, : 197 - 200
  • [22] Maximizing edge-ratio is NP-complete
    Noble, Steven D.
    Hansen, Pierre
    Mladenovic, Nenad
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (18) : 2276 - 2280
  • [23] Automatically Solving NP-Complete Problems on a Quantum Computer
    Hu, Shaohan
    Liu, Peng
    Chen, Chun-Fu
    Pistoia, Marco
    PROCEEDINGS 2018 IEEE/ACM 40TH INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING - COMPANION (ICSE-COMPANION, 2018, : 258 - 259
  • [24] APPROXIMATION ALGORITHMS FOR NP-COMPLETE PROBLEMS ON PLANAR GRAPHS
    BAKER, BS
    JOURNAL OF THE ACM, 1994, 41 (01) : 153 - 180
  • [25] Sublinear P system solutions to NP-complete problems
    Dinneen, Michael J.
    Henderson, Alec
    Nicolescu, Radu
    THEORETICAL COMPUTER SCIENCE, 2023, 958
  • [26] Survey of polynomial transformations between NP-complete problems
    Ruiz-Vanoye, Jorge A.
    Perez-Ortega, Joaquin
    Pazos R, Rodolfo A.
    Diaz-Parra, Ocotlan
    Frausto-Solis, Juan
    Fraire Huacuja, Hector J.
    Cruz-Reyes, Laura
    Martinez F, Jose A.
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2011, 235 (16) : 4851 - 4865
  • [27] An optical fiber network oracle for NP-complete problems
    Kan Wu
    Javier García de Abajo
    Cesare Soci
    Perry Ping Shum
    Nikolay I Zheludev
    Light: Science & Applications, 2014, 3 (2) : e147 - e147
  • [28] Two slightly-entangled NP-Complete problems
    Orús, R
    QUANTUM INFORMATION & COMPUTATION, 2005, 5 (06) : 449 - 455
  • [29] Solving NP-complete problems in the tile assembly model
    Brun, Yuriy
    THEORETICAL COMPUTER SCIENCE, 2008, 395 (01) : 31 - 46
  • [30] An optical fiber network oracle for NP-complete problems
    Wu, Kan
    Garcia de Abajo, Javier
    Soci, Cesare
    Shum, Perry Ping
    Zheludev, Nikolay I.
    LIGHT-SCIENCE & APPLICATIONS, 2014, 3
12345