ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Some simple but interesting results concerning the P ?= NP Problem
Full text PdfPdf (177 KB)
Source ACM SIGACT News archive
Volume 35 ,  Issue 3  (September 2004) table of contents
Pages: 94 - 97  
Year of Publication: 2004
ISSN:0163-5700
Author
Antti Ylikoski  Helsinki University of Technology
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 22,   Citation Count: 0
Additional Information:

abstract   references  

Tools and Actions: Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/1027914.1027915
What is a DOI?

ABSTRACT

In this paper, I discuss some properties of two functions, which I call f1() and f2(), which are interesting from the point of view of the <i>P</i> ?= <i>NP</i> problem. The both functions <i>f</i>1() and <i>f</i>2() concern the problem of solving a nondeterministic polynomial-time problem deterministically in a polynomial time. Based on the results, I finally outline a research program to study the <i>P</i> ?= <i>NP</i> problem.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
{Davis-Sigal-Weyuker1994} {Davis-Sigal-Weyuker1994} Martin D. Davis, Ron Sigal, Elaine J. Weyuker: Computability, Complexity, and Languages, Morgan Kaufmann and Academic Press, 1994, ISBN 0-12-206382-1.
 
2
Neil D. Jones, Computability and complexity: from a programming perspective, MIT Press, Cambridge, MA, 1997

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player