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 条

[31] The Bandwidth Allocation Problem in the ATM network model is NP-complete
Vedantham, S
Iyengar, SS
INFORMATION PROCESSING LETTERS, 1998, 65 (04) : 179 - 182
[32] Three-player Col played on trees is NP-complete
Cincotti, Alessandro
IMECS 2009: INTERNATIONAL MULTI-CONFERENCE OF ENGINEERS AND COMPUTER SCIENTISTS, VOLS I AND II, 2009, : 445 - 447
[33] Three-player Hackenbush played on strings is NP-complete
Cincotti, Alessandro
IMECS 2008: INTERNATIONAL MULTICONFERENCE OF ENGINEERS AND COMPUTER SCIENTISTS, VOLS I AND II, 2008, : 226 - 230
[34] The edge split reconstruction problem for chemical trees is NP-complete
Li, XL
Zhang, XY
MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY, 2004, (51) : 205 - 210
[35] The Sudoku completion problem with rectangular hole pattern is NP-complete
Bejar, Ramon
Fernandez, Cesar
Mateu, Caries
Valls, Magda
DISCRETE MATHEMATICS, 2012, 312 (22) : 3306 - 3315
[36] The weighted independent domination problem is NP-complete for chordal graphs
Chang, GJ
DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) : 351 - 352
[37] Reliable identification of bounded-length viruses is NP-complete
Spinellis, D
IEEE TRANSACTIONS ON INFORMATION THEORY, 2003, 49 (01) : 280 - 284
[38] THE EDGE HAMILTONIAN PATH PROBLEM IS NP-COMPLETE FOR BIPARTITE GRAPHS
LAI, TH
WEI, SS
INFORMATION PROCESSING LETTERS, 1993, 46 (01) : 21 - 26
[39] Permuted max-algebraic eigenvector problem is NP-complete
Butkovic, P.
LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (8-9) : 1874 - 1882
[40] Lexicalized Non-Local MCTAG with Dominance Links is NP-Complete
Champollion L.
Journal of Logic, Language and Information, 2011, 20 (3) : 343 - 359

← 1 2 3 4 5 →