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 条

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

EITER, T ;

KILPELAINEN, P ;

MANNILA, H .

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

[42] 2-subcoloring is NP-complete for planar comparability graphs [J].

Ochem, Pascal .

INFORMATION PROCESSING LETTERS, 2017, 128 :46-48

[43] MPF Problem over Modified Medial Semigroup Is NP-Complete [J].

Sakalauskas, Eligijus ;

Mihalkovich, Aleksejus .

SYMMETRY-BASEL, 2018, 10 (11)

[44] TRAINING A 3-NODE NEURAL NETWORK IS NP-COMPLETE [J].

BLUM, AL ;

RIVEST, RL .

NEURAL NETWORKS, 1992, 5 (01) :117-127

[45] The Sudoku completion problem with rectangular hole pattern is NP-complete [J].

Bejar, Ramon ;

Fernandez, Cesar ;

Mateu, Caries ;

Valls, Magda .

DISCRETE MATHEMATICS, 2012, 312 (22) :3306-3315

[46] Finding a Nash equilibrium in spatial games is an NP-complete problem [J].

Baron, R ;

Durieu, J ;

Haller, H ;

Solal, P .

ECONOMIC THEORY, 2004, 23 (02) :445-454

[47] The harmonious coloring problem is NP-complete for interval and permutation graphs [J].

Asdre, Katerina ;

Ioannidou, Kyriaki ;

Nikolopoulos, Stavros D. .

DISCRETE APPLIED MATHEMATICS, 2007, 155 (17) :2377-2382

[48] Eulerian disjoint paths problem in grid graphs is NP-complete [J].

Marx, D .

DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) :336-341

[49] Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry [J].

Khot, Subhash .

PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS, VOL IV: INVITED LECTURES, 2010, :2676-2697

[50] Some NP-Complete Results on Signed Mixed Domination Problem [J].

Yancai ZHAO ;

Huahui SHANG ;

HAbdollahzadeh AHANGAR ;

NJafari RAD .

Journal of Mathematical Research with Applications, 2017, 37 (02) :163-168

← 1 2 3 4 5 →