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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 30, 1993
Accession Number
ADA278598

Entities

People

  • Joseph F. Traub

Organizations

  • Columbia University

Tags

Communities of Interest

  • Biomedical
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computational Science
  • Computer Science
  • Computers
  • Differential Equations
  • Digital Computers
  • Engineering
  • Equations
  • Floating Point Operations
  • Integral Equations
  • Mathematical Models
  • Monte Carlo Method
  • New York
  • Number Theory
  • Numerical Analysis
  • Theoretical Computer Science

Readers

  • Academic Conference Management
  • Military History
  • Neural Network Machine Learning.