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
Lowenheim, L
[J]. 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
ROBINSON, JA
[J]. 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
URQUHART, A
[J]. JOURNAL OF THE ACM, 1987, 34 (01) : 209 - 219
[18] SOME APPLICATIONS OF A THEOREM OF RADO
WELSH, DJA
[J]. MATHEMATIKA, 1968, 15 (30P2) : 199 - &

← 1 2 →