MANY HARD EXAMPLES FOR RESOLUTION

被引：240

作者：

CHVATAL, V ^{[1
]}

SZEMEREDI, E ^{[1
]}

机构：

[1] HUNGARIAN ACAD SCI,INST MATH,H-1361 BUDAPEST 5,HUNGARY

来源：

JOURNAL OF THE ACM | 1988年 / 35卷 / 04期

关键词：

Mathematical Techniques - Graph Theory - Probability - Random Processes;

D O I：

10.1145/48014.48016

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

It is proved that for every choice of positive integers c and k such that k ≥ 3 and c2-k ≥ 0.7, there is a positive number Ε such that, with probability tending to 1 as n tends to ∞, a randomly chosen family of cn clauses of size k over n variables is unsatisfiable, but every resolution proof of its unsatisfiability must generate at least (1 + Ε)n clauses. The proof makes use of random hypergraphs.

引用

页码：759 / 768

页数：10

共 18 条

[11] Solution of equations in logical area calculation [J].

Lowenheim, L .

MATHEMATISCHE ANNALEN, 1910, 68 :169-207

[12]

Lowenheim L, 1908, SITZUNGSBERICHTE BER, V7, P89

[13]

Rado R., 1942, Q J MATH OXFORD, V13, P83

[14] A MACHINE-ORIENTED LOGIC BASED ON RESOLUTION PRINCIPLE [J].

ROBINSON, JA .

JOURNAL OF THE ACM, 1965, 12 (01) :23-&

[15]

Rudeanu S., 1968, BOOLEAN METHODS OPER

[16]

Tseitin G., 1968, STUDIES CONSTRUCTI 2, P115

[17] HARD EXAMPLES FOR RESOLUTION [J].

URQUHART, A .

JOURNAL OF THE ACM, 1987, 34 (01) :209-219

[18] SOME APPLICATIONS OF A THEOREM OF RADO [J].

WELSH, DJA .

MATHEMATIKA, 1968, 15 (30P2) :199-&

← 1 2 →