BLOCKSUM is NP-Complete

被引：7

作者：

Haraguchi, Kazuya ^{[1
]}

Ono, Hirotaka ^{[2
]}

机构：

[1] Ishinomaki Senshu Univ, Fac Sci & Engn, Dept Informat Technol & Elect, Ishinomaki, Miyagi 9868580, Japan

[2] Kyushu Univ, Fac Econ, Dept Econ Engn, Fukuoka 8128581, Japan

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2013年 / E96D卷 / 03期

关键词：

NP-completeness; combinatorial puzzle; Latin square; BLOCKSUM;

D O I：

10.1587/transinf.E96.D.481

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

BLOCKSUM, also known as KEISANBLOCK in Japanese, is a Latin square filling type puzzle, such as Sudoku. In this paper, we prove that the decision problem whether a given instance of BLOCKSUM has a solution or not is NP-complete.

引用

页码：481 / 488

页数：8

共 50 条

[31] Packing cubes into a cube is NP-complete in the strong sense [J].

Lu, Yiping ;

Chen, Danny Z. ;

Cha, Jianzhong .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (01) :197-215

[32] Solving NP-Complete Akari games with deep learning [J].

Sbrana, Attilio ;

Bizarro Mirisola, Luiz Gustavo ;

Soma, Nei Yoshihiro ;

Lima de Castro, Paulo Andre .

ENTERTAINMENT COMPUTING, 2023, 47

[33] Switching to Hedgehog-Free Graphs Is NP-Complete [J].

Jelinkova, Eva .

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011, 2011, 6648 :463-470

[34] Autoreducibility of NP-Complete Sets under Strong Hypotheses [J].

Hitchcock, John M. ;

Shafei, Hadi .

COMPUTATIONAL COMPLEXITY, 2018, 27 (01) :63-97

[35] FINDING A HOMOMORPHISM BETWEEN 2 WORDS IS NP-COMPLETE [J].

EHRENFREUCHT, A ;

ROZENBERG, G .

INFORMATION PROCESSING LETTERS, 1979, 9 (02) :86-88

[36] Automatic Evaluation of Reductions between NP-Complete Problems [J].

Creus, Carles ;

Fernandez, Pau ;

Godoy, Guillem .

THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2014, 2014, 8561 :415-421

[37] Multiple Kernel Support Vector Machine Problem Is NP-Complete [J].

Carlos Padierna, Luis ;

Martin Carpio, Juan ;

del Rosario Baltazar, Maria ;

Jose Puga, Hector ;

Joaquin Fraire, Hector .

NATURE-INSPIRED COMPUTATION AND MACHINE LEARNING, PT II, 2014, 8857 :152-159

[38] Local edge-connectivity augmentation in hypergraphs is NP-complete [J].

Kiraly, Zoltan ;

Cosh, Ben ;

Jackson, Bill .

DISCRETE APPLIED MATHEMATICS, 2010, 158 (06) :723-727

[39] RECOGNIZING RENAMABLE GENERALIZED PROPOSITIONAL HORN FORMULAS IS NP-COMPLETE [J].

EITER, T ;

KILPELAINEN, P ;

MANNILA, H .

DISCRETE APPLIED MATHEMATICS, 1995, 59 (01) :23-31

[40] FINDING HAMILTONIAN CIRCUITS IN ARRANGEMENTS OF JORDAN CURVES IS NP-COMPLETE [J].

IWAMOTO, C ;

TOUSSAINT, GT .

INFORMATION PROCESSING LETTERS, 1994, 52 (04) :183-189

← 1 2 3 4 5 →