SHORT PROPOSITIONAL FORMULAS REPRESENT NONDETERMINISTIC COMPUTATIONS

被引：37
作者：
COOK, SA
机构：
来源：
INFORMATION PROCESSING LETTERS | 1988年 / 26卷 / 05期
关键词：
D O I：
10.1016/0020-0190(88)90152-4
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
引用
收藏
页码：269 / 270
页数：2
相关论文
共 6 条
  • [1] [Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047
  • [2] DEWDNEY AK, 1985, 141 U W ONT DEP COMP
  • [3] RELATIONS AMONG COMPLEXITY MEASURES
    PIPPENGER, N
    FISCHER, MJ
    [J]. JOURNAL OF THE ACM, 1979, 26 (02) : 361 - 381
  • [4] ROBSON JM, 1979, 2ND P AUSTR COMP SCI, P62
  • [5] SATISFIABILITY IS QUASILINEAR COMPLETE IN NQL
    SCHNORR, CP
    [J]. JOURNAL OF THE ACM, 1978, 25 (01) : 136 - 145
  • [6] STEARNS RE, 1986, 8621 STAT U NEW YORK
1