Record number :
Title of article :
NP-completeness of kSAT and multifractals Original Research Article
Author/Authors :
Yuzuru Sato، نويسنده , , Makoto Taiji، نويسنده , , Takashi Ikegami، نويسنده ,
Issue Information :
دوهفته نامه با شماره پیاپی سال 1999
Pages :
From page :
To page :
Abstract :
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.
Journal title :
Computer Physics Communications
Journal title :
Computer Physics Communications
Serial Year :
Link To Document :