On the relative complexity of some languages in NC1

被引：0
|
作者：
Barrington, David A.Mix [1 ]
Corbett, James [1 ]
机构：
[1] Univ of Massachusetts, United States
来源：
Information Processing Letters | 1989年 / 32卷 / 05期
关键词：
Computational Complexity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
引用
收藏
页码：251 / 256
相关论文
共 50 条
  • [1] Quantified propositional calculus and a second-order theory for NC1
    Cook, S
    Morioka, T
    ARCHIVE FOR MATHEMATICAL LOGIC, 2005, 44 (06) : 711 - 749
  • [2] Quantified propositional calculus and a second-order theory for NC1
    Stephen Cook
    Tsuyoshi Morioka
    Archive for Mathematical Logic, 2005, 44 : 711 - 749
  • [3] The Complexity of Equality Constraint Languages
    Manuel Bodirsky
    Jan Kára
    Theory of Computing Systems, 2008, 43 : 136 - 158
  • [4] The complexity of equality constraint languages
    Bodirsky, Manuel
    Kara, Jan
    THEORY OF COMPUTING SYSTEMS, 2008, 43 (02) : 136 - 158
  • [5] The complexity of equality constraint languages
    Bodirsky, Manuel
    Kara, Jan
    COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2006, 3967 : 114 - 126
  • [6] The complexity of counting quantifiers on equality languages
    Martin, Barnaby
    Pongracz, Andras
    Wrona, Michal
    THEORETICAL COMPUTER SCIENCE, 2017, 670 : 56 - 67
  • [7] The relative complexity of approximate counting problems
    Dyer, M
    Goldberg, LA
    Greenhill, C
    Jerrum, M
    ALGORITHMICA, 2004, 38 (03) : 471 - 500
  • [8] The Relative Complexity of Approximate Counting Problems
    Martin Dyer
    Leslie Ann Goldberg
    Catherine Greenhill
    Mark Jerrum
    Algorithmica , 2004, 38 : 471 - 500
  • [9] On the computational and descriptional complexity of multi-pattern languages
    Xie, Jingnan
    Hunt Iii, Harry B.
    Stearns, Richard E.
    THEORETICAL COMPUTER SCIENCE, 2025, 1030
  • [10] The Complexity of Minimal Inference Problem for Conservative Constraint Languages
    Wrona, Michal
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2019, 20 (02)
12345