ON THE COMPLEXITY OF TEST CASE GENERATION FOR NP-HARD PROBLEMS

被引：12
作者：
SANCHIS, LA [1 ]
机构：
[1] UNIV ROCHESTER,DEPT COMP SCI,ROCHESTER,NY 14627
来源：
INFORMATION PROCESSING LETTERS | 1990年 / 36卷 / 03期
关键词：
approximation algorithms; Computational complexity; generation; NP-completeness; test cases;
D O I：
10.1016/0020-0190(90)90082-9
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
[No abstract available]
引用
收藏
页码：135 / 140
页数：6
相关论文
共 17 条
  • [1] THE BOOLEAN HIERARCHY .1. STRUCTURAL-PROPERTIES
    CAI, JY
    GUNDERMANN, T
    HARTMANIS, J
    HEMACHANDRA, LA
    SEWELSON, V
    WAGNER, K
    WECHSUNG, G
    [J]. SIAM JOURNAL ON COMPUTING, 1988, 17 (06) : 1232 - 1252
  • [2] THE BOOLEAN HIERARCHY .2. APPLICATIONS
    CAI, JY
    GUNDERMANN, T
    HARTMANIS, J
    HEMACHANDRA, LA
    SEWELSON, V
    WAGNER, K
    WECHSUNG, G
    [J]. SIAM JOURNAL ON COMPUTING, 1989, 18 (01) : 95 - 111
  • [3] Floyd S., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P322, DOI 10.1109/SFCS.1986.18
  • [4] Garey M.R., 1979, COMPUTERS INTRACTABI, V174
  • [5] HARMANIS J, 1983, 15TH P ANN ACM S THE, P382
  • [6] ON SPARSE SETS IN NP-P
    HARTMANIS, J
    [J]. INFORMATION PROCESSING LETTERS, 1983, 16 (02) : 55 - 60
  • [7] AN INTRODUCTION TO THE ANALYSIS OF APPROXIMATION ALGORITHMS
    KAN, AHGR
    [J]. DISCRETE APPLIED MATHEMATICS, 1986, 14 (02) : 171 - 185
  • [8] CONSTRUCTING TEST CASES FOR PARTITIONING HEURISTICS
    KRISHNAMURTHY, B
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1987, 36 (09) : 1112 - 1114
  • [9] SPARSE SETS IN NP-P - RELATIVIZATIONS
    KURTZ, SA
    [J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (01) : 113 - 119
  • [10] OPTIMIZATION PROBLEMS AND THE POLYNOMIAL HIERARCHY
    LEGGETT, EW
    MOORE, DJ
    [J]. THEORETICAL COMPUTER SCIENCE, 1981, 15 (03) : 279 - 289
12