Computational lower bounds using diagonalization — II

M V, Panduranga Rao (2010) Computational lower bounds using diagonalization — II. Resonance, 15 (4). pp. 337-346. ISSN 0971-8044

Full text not available from this repository. (Request a copy)

Abstract

In the previous article1 we discussed some basic ideas in theoretical computer science like decision problems, languages, Turing machines, their encodings as strings over a finite alphabet, Universal Turing machines and some important computational complexity classes. In this article we discuss a powerful technique called diagonalization for arriving at lower bounds on computing resources for deciding languages. We will discuss the method, its success and possible limitations.

[error in script]
IITH Creators:
IITH CreatorsORCiD
M V, Panduranga RaoUNSPECIFIED
Item Type: Article
Uncontrolled Keywords: Computational lower bounds,
Subjects: Computer science
Computer science > Systems
Computer science > Computer programming, programs, data
Computer science > Special computer methods
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 06 May 2021 07:34
Last Modified: 06 May 2021 07:34
URI: http://raiithold.iith.ac.in/id/eprint/7754
Publisher URL: http://doi.org/10.1007/s12045-010-0027-3
OA policy: https://v2.sherpa.ac.uk/id/publication/23136
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 7754 Statistics for this ePrint Item