• Articles • Previous Articles     Next Articles

Some Structural Properties of SAT

LIU Tian;   

  1. Department of Computer Science and Technology; Peking University; Beijing 100871; P.R. China;
  • Online:2000-09-10 Published:2000-09-10

The following four conjectures about structural properties of SAT are studied in this paper. (1) SAT ∈ PSPARSEnNP; (2) SAT ∈ SRTDtt; (3) SAT ∈ PttbAPP; (4) FPttSAT = FPlogSAT. It is proved that some pairs of these conjectures imply P = NP, for example, if SAT E pSPARsEnNP and SAT 6 PttbAPP, or if SAT E SRTDtt and SAT E PttbAPP, then P = NP. This improves previous results in literature.

Key words: group-based protocol; group-based architecture; group-based routing algorithm; large networks;

[1] Naik A N, Selman A L. A note on P-selective sets and on adaptive versus nonadaptive queries to NP. In Proceedings of the 11th Annual IEEE Confererce on Computational Complexity, IEEE Computer Society Press, 1996, pp.2-15.

[2] Buhrman H. Fortnow L Thierauf T. Six hypotheses in search of a theorem. In Proceedings of the 12th Annual IEEE Corfererce on Computational Complexity, IEEE Computer Society Press, 1997, pp.2-12.

[3] Ogiwara M, Watanabe O. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal or Computing, 1991, 20: 471-483. ……….
[1] Jaime Lloret, Miguel Garcia, Jesus Tomás, and Fernando Boronat. GBP-WAHSN: A Group-Based Protocol for Large Wireless Ad Hoc and Sensor Networks [J]. , 2008, 23(3): 461-480 .
Full text



No Suggested Reading articles found!

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved