The minimal logically-defined NP-complete problem

被引：0

作者：

Barbanchon, R ^{[1
]}

Grandjean, E ^{[1
]}

机构：

[1] Univ Caen, GREYC, F-14032 Caen, France

来源：

STACS 2004, PROCEEDINGS | 2004年 / 2996卷

关键词：

computational complexity; descriptive complexity; finite model theory; second-order logic; NP-completeness; parsimony;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We exhibit an NP-complete problem defined by an existential monadic second-order (EMSO) formula over functional structures that is: 1. minimal under several syntactic criteria (i.e., any EMSO formula that further strengthens any criterion defines a PTIME problem even if all other criteria are weakened); 2. unique for such restrictions, up to renamings and symmetries. Our reductions and proofs are surprisingly very elementary and simple in comparison with some recent similar results classifying existential second-order formulas over relational structures according to their ability either to express NP-complete problems or to express only PTIME ones.

引用

页码：338 / 349

页数：12

共 14 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Barbanchon G, 2002, LECT NOTES COMPUT SC, V2471, P397

[3]

COURCELLE B, 1997, DESCRIPTIVE COMPLEXI, P33

[4]

DURAND A, 2003, IN PRESS THEORETICAL

[5] Existential second-order logic over strings [J].

Eiter, T ;

Gottlob, G ;

Gurevich, Y .

JOURNAL OF THE ACM, 2000, 47 (01) :77-131

[6]

Fagin Ronald, 1974, Complexity of Computation, P43

[7]

GOTLOB G, 2000, FDN COMPUTER SCI, P664

[8]

GRADEL E, 1991, THEORETICAL COMPUTER, V101, P35

[9]

GRANDJEAN E, 2004, IN PRESS J COMPUTER

[10] The complexity of planar counting problems [J].

Hunt, HB ;

Marathe, MV ;

Radhakrishnan, V ;

Stearns, RE .

SIAM JOURNAL ON COMPUTING, 1998, 27 (04) :1142-1167

← 1 2 →