NP-completeness of kSAT and multifractals

被引：2

作者：

Sato, Y

Taiji, M

Ikegami, T

机构：

[1] Univ Tokyo, Inst Phys, Grad Sch Arts & Sci, Meguro Ku, Tokyo 153, Japan

[2] Inst Statistic Math, Minato Ku, Tokyo 106, Japan

来源：

COMPUTER PHYSICS COMMUNICATIONS | 1999年 / 121卷

关键词：

D O I：

10.1016/S0010-4655(99)00278-7

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The geometrical structure of a formal language class is studied in relation with its time-complexity. A typical NP-complete problem, kSAT, is discussed by visualizing its problem space and a strict connection is made between the self-similarity and the time-complexity of the languages by constructing adequate iterated function systems (IFSs), There exist IFS classes which generate whole satisfiable Boolean expressions embedded on a unit hyper-cube, Our numerical results for the Hausdorff dimension of kSAT suggest the difference of IFS classes for 2 and 3SAT. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：51 / 53

页数：3