Accession Number:

ADA278598

Title:

Can We Break Intractability Using Randomization or the Average Case Setting?

Descriptive Note:

Final rept. 1 Sep 1991-31 Aug 1993

Corporate Author:

COLUMBIA UNIV NEW YORK DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Traub, Joseph F.

Report Date:

1993-09-30

Pagination or Media Count:

32.0

Abstract:

The following papers cover results of the researchers and make up the final report 1 A Surprising and Important New Result, by J F Traub, Feb 25, 1994, 2 Recent Progress in Information-Based Complexity, by J F Traub and H wozinakowski, Invited Paper, Bulletin European Assoc for Theoretical Computer Science, Oct 1993, Number 51, pages 141-154 and 3 Breaking Intractability, by J F Traub and H Woziakowski, published as cover story of Scientific American, Jan 1994.

Descriptors:

• *COMPUTATIONS
• *MONTE CARLO METHOD
• *PROBLEM SOLVING
• PSEUDO RANDOM SYSTEMS

Subject Categories:

• Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE