NDLI: That really is a hard problem you've spent six months working on: A tutorial on NP-complete problems

Please wait, while we are loading the content...

The profitability of career planning

A tutorial on natural-language processing

Presentation abstract: A tutorial on local networks

Tutorial on data base machines

Structured systems analysis tutorial

Robots and their impact on employment

Current topics in fortran development: Macros and Compile-Time Processing

Industrial real-time fortran

Environmental inquiry and general precision data type features fort he next fortran standard

Data abstraction and hiding in Fortran

Array processing - principles and practice

Performance of distributed software implemented by a contention bus

The design of a distributed kernel

Auditing for secure statistical databases

Methods for system simulation on a restricted data flow architecture

Strategies for database schema acquisition and design

Expert systems seminar

The may company california network a case study

Data base machines (Part II)

Structured systems analysis (Part II)

Anintroduction to Ada

Medical information systems integration (Panel Discussion)

Computers and the improvement of writing

The structure of “data structures”

Structured Systems Analysis and the Problem Statement Language (PSL)(8) as a combined methodology in the teaching of System Analysis and Design

Some ideas on the educational use of computers

Computer chess: Master level play in 1981?

A survey of enhancements to the alpha-beta algorithm

An introduction to ADA (Part II)

Careers for computing professionals

Women in management - entering and growing(ACM '81 Panel Session Abstract)

Computer contracting and litigation

Queueing theory

Local networking by ring, ethernet, broadband, and PABX—perspectives from the field

Tutorial: Microcode compaction is smaller always better?

Metrics in software quality assurance

An overview of the “1981 ACM SIGMETRICS Workshop/Symposium on Measurement and Evaluation of Software Quality”

Color Graphics in Education, Art and Industry

An $ADA^{TM}$ compatible specification language

Towards a practical specification language

Capsules: A data abstraction facility for Pascal

Conformant arrays and strong typing

“Ada after one year: How have government politics, industry concerns, and academia mixed?”

1981 A.C.M. annual conference position paper computer crime laws and the computing professional: What you don't know hay hurt you

Software Engineering tutorial

Educational development opportunities for computer professionals

Continuing education services of the IEEE computer society

Status of graduate software engineering education

Self-Assessment as a precursor to professional development

Industrial software training opportunities for computer professionals

The role of certification in fostering professional development in the field of computing

Interactive operating systems for small computers (Panel Discussion)

Computer-aided design of electrical circuits Simulation techniques (A Tutorial)

Gate array layout automation: A tutorial

Perspectives: Computers, tools, and people

Stress management for the computing professional

“The technical issues confronting Ada”

PDL/Ada—a design language based on Ada

The computer professional as an expert witness

Software engineering (Part II)

Certification for the computer professional - individual preparation strategies

Automatic information retrieval (Tutorial and Panel Discussion)

Automatic indexing

The changing face of information retrieval systems

Automated abstracting: A re-evaluation

Automatic diagnosis of computer faults using computer systems

Fault prediction and dynamic error analysis in computer systems

The architecture of Tandem's NonStop system

DART: Expert systems for automated computer fault diagnosis

The changing role of the EDP manager

Pseudo-oracles for non-testable programs

Computer network operations—making it all go at once

Input-directed program design

Quantifying software quality

Information resource management(IRM): Theory applied to three environments

Information resource management theory training

Information resources management (IRM): Where did it come from and where is it going

Information Resource Management: Theory applied

State of the art issues in distributed databases (Panel session): Site autonomy issues in the R@@@@ distributed database system

State of the art issues in distributed databases (Panel Session): Form-Flow Application Development

State of the art issues in distributed databases (Panel session): The efficacy of replicated data

State of the art issues in distributed databases (ACM 81 Panel session): Transaction processing issues in the distributed database tested system

The ISO Reference Model of Open Systems Interconnection: A first tutorial

The Computer Software Products Industry in the '80s

Elementary computer literacy (SIGCAS)

That really is a hard problem you've spent six months working on: A tutorial on NP-complete problems

Some experiments in man-machine interaction relevant to computer assisted instruction

An experimental vehicle for the user/filing-system interface

Pictorial man-machine communication

Producing learning material for the intelligent videodisc

Computer assisted learning using videodiscs

Videodiscs and microprocessors the issue of useability

Computers in schools grades K-12 (Panel Discussion)

Computers in Hollywood

The turnover issue in EDP personnel

Using new technology for systems documentation: Specifications for an on-line documentation system for the paperless office

Compatibility: A barrier to applying technology to documentation

Demonstration of a videodisc system for the classroom

Educational pathways to computing careers in health care: Education for leadership in the health computing profession

Educational preparation for support-level careers in health computing

That really is a hard problem you've spent six months working on: A tutorial on NP-complete problems

Content Provider	ACM Digital Library
Author	Lueker, George Robertson, Edward
Abstract	The property of being “NP-complete” and the “P &equil;? NP” question are recognized as important theoretical concepts with which a practicing computer scientist should be acquainted. This tutorial will briefly introduce a simple model in which the significance of “NP-completeness” is discussed and will illustrate what makes a problem NP-complete with several examples. The second part of the tutorial discusses some of the ways of dealing with NP-complete problems. The computational models used in this presentation are deliberately extremely simple. The very simplicity of the model allows it to easily capture an important property of NP-complete problems: finding a solution may be difficult, but if one can guess (or be given) a solution, the validity of this solution can easily be tested. This is the first part of the definition of NP-completeness and puts a (very high) upper limit on how difficult an NP-complete problem can be. The second part of the definition gives a lower limit with a requirement that a problem be as hard as a well-known class of difficult questions. The tutorial will illustrate how relative difficulty is established and will discuss the expected but unproved absolute difficulty of NP-complete problems. The second half of the tutorial will be devoted to examining the implications of NP-completeness. It will be seen that NP-completeness is not always as serious limitation as it might appear to be. For example, sometimes it is possible to compute an approximation in a reasonable amount of time, with a guarantee that the approximation is not too far from the true optimum value. Sometimes it is possible to do a probabilistic analysis which shows that an algorithm does well on the average. Thus the notion of NP-completeness can help people redirect their efforts effectively by giving them some idea of what are realistic goals.
Starting Page	293
Ending Page	294
Page Count	2
File Format	PDF
ISBN	0897910494
DOI	10.1145/800175.809904
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1981-01-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in