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 Creators ORCiD M V, Panduranga Rao UNSPECIFIED
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:	Author

Actions (login required)

View Item

Statistics for this ePrint Item