THE P-NP PROPERTIES OF BOUNDED QUERY COMPUTATIONS
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    his paper restricts oracle Turing machine to query its oracle in an accepting computation, and obtains result: there exist infinite number of recursive sets A, B, A',B', A", B", A, B, which are not equivalent satisfying properties: P(A,q) =P(A,q+ 1 ), P(B,q ) ≠P(B,q+1)p(a',q)=P(A' ),P(B',q)≠P(B' ),NP(A",q) = NP(A",q + 1),NP(B",q) ≠ (B",q+ 1 ),NP (A,q) =NP(A), NP(B,q)≠NP(B).

    Reference
    Related
    Cited by
Get Citation

吕义忠,刘建斌.受限外部信息源计算的P─NP性质.软件学报,1994,5(4):40-48

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 27,1991
  • Revised:December 21,1991
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063