[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Some structural properties of SAT

  • Published:
Journal of Computer Science and Technology Aims and scope Submit manuscript

Abstract

The following four conjectures about structural properties of SAT are studied in this paper. (1) SAT ∈P SPARSE∩NP; (2) SAT ∈SRTD tt; (3) SAT ∈P bAPP tt ; (4)FP SAT tt . It is proved that some pairs of these conjectures implyP=NP, for example, if\(SAT \in P^{SPARSE \cap NP} \) and SAT ∈p bAPP tt , or if SAT ∈SRTD tt and SAT ∈P bAPP tt , thenP=NP. This improves previous results in literature.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Naik A N, Selman A L. A note onP-selective sets and on adaptive versus nonadaptive queries to NP. InProceeding of the 11th Annual IEEE Conference 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. InProceedings of the 12th Annual IEEE Conference 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 on Computing, 1991, 20: 471–483.

    Article  MATH  MathSciNet  Google Scholar 

  4. Ogihara M. Polynomial-time membership comparable sets.SIAM Journal on Computing, 1995, 24: 1068–1081.

    Article  MATH  MathSciNet  Google Scholar 

  5. Karp R M, Ripton R J. Some connections between nonuniform and uniform complexity classes. InProceedings of the 12th Annual ACM Symposium on the Theory of Computing, ACM Press, 1980, pp.302–309.

  6. Köbler J, Watanabe O. New collapse consequences of NP having small circuits.SIAM Journal on Computing, 1999, 28: 311–324.

    Article  MathSciNet  Google Scholar 

  7. Lutz J H, Mayordomo E. Measure, stochasticity, and the density of hard languages.SIAM Journal on Computing, 1994, 23: 762–779.

    Article  MATH  MathSciNet  Google Scholar 

  8. Wang Y. NP-hard sets are superterse unless NP is small. Technical Report TR97-021, Electronic Colloquium on Computational Cmplexity, URL: http://www.eccc.uni-trier.de/eccc/,1996.

  9. Kadin J.N NP[log] and sparse Turing-complete sets for NP.Journal of Computer and System Sciences, 1989, 39: 282–298.

    Article  MATH  MathSciNet  Google Scholar 

  10. Arvind V, Toran J. Sparse sets, approximable sets, and parallel queries to NP. Technical Report TR98-027, Electronic Colloquium on Computational Cmplexity, URL: http://www.eccc.uni-trier.de/eccc/, 1998.

  11. Watanabe O, Toda S. Structural analysis on the complexity of inverse functions.Mathematical Systems Theory, 1993, 26: 203–214.

    Article  MATH  MathSciNet  Google Scholar 

  12. Buhrman H, Thierauf T. The complexity of generating and checking proofs of membership. InProceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science #1046, Springer-Verlag, 1996, pp.75–86.

  13. Buhrman H, Fortnow L. Resource-bounded Kolmogorov complexity revisited. InProceedings of the 24th Annual International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science #1200, Springer-Verlag, 1997, pp.105–116.

  14. Amir A, Beigel R, Gasarch W I. Some connections between bounded-query classes and nonuniform complexity. InProceedings of the 5th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, 1990, pp.232–243.

  15. Beigel R. NP hard sets areP superterse unlessR=NP. Technical Report 88-04, Department of Computer Science, The Johns Hopkins University, 1988.

  16. Toda S. On polynomial time truth-table reducibility of intractable sets toP-selective sets.Mathematical Systems Theory, 1991, 24: 69–82.

    Article  MATH  MathSciNet  Google Scholar 

  17. Selman A. A taxonomy of complexity classes of functions.Journal of Computer and System Sciences, 1994, 48: 357–381.

    Article  MATH  MathSciNet  Google Scholar 

  18. Balcázar J L, Díaz J, Gabaró J. Structural Complexity Theory, I, II. Springer-Verlag, 1988, 1990.

  19. Papadimitriou C H. Computational Complexity. Addison-Wesley, 1994.

  20. Köbler J, Thierauf T. Complexity-restricted advice functions.SIAM Journal on Computing, 1994, 23: 261–275.

    Article  MATH  MathSciNet  Google Scholar 

  21. Krentel M W. The complexity of optimization problems.Journal of Computer and System Sciences, 1988, 36: 490–509.

    Article  MATH  MathSciNet  Google Scholar 

  22. Selman A. Much ado about functions. InProceedings of the 11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, 1996, pp.2–14.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Technology, Peking University, 100871, Beijing, P.R. China

    Liu Tian

Authors
  1. Liu Tian
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Liu Tian.

Additional information

This work is supported by the key project fund of China’s Ninth Five-Year Plan and the Science Foundation of Peking University.

LIU Tian received the B.S. degree from University of Science and Technology of China in 1989, the M.S. degree in theory of computer science from Beijing Computer Institute in 1992, and the Ph.D. degree in computer software and theory. Peking University in 1999. His main research interests include computational complexity theory.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, T. Some structural properties of SAT. J. Comput. Sci. & Technol. 15, 439–444 (2000). https://doi.org/10.1007/BF02950407

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02950407

Keywords

Search

Navigation