Computability and Complexity Theory by Steven Homer & Alan L. Selman
Author:Steven Homer & Alan L. Selman
Language: eng
Format: epub
Publisher: Springer US, Boston, MA
In this chapter we expand more broadly on the idea of using a subroutine for one problem in order to efficiently solve another problem. By doing so, we make precise the notion that the complexity of a problem B is related to the complexity of A – that there is an algorithm to efficiently accept Brelative to an algorithm to efficiently decide A. As in Sect. 3.9, this should mean that an acceptor for B can be written as a program that contains subroutine calls of the form “x ∈ A,” which returns True if the Boolean test is true and returns False otherwise. Recall that the algorithm for accepting B is called a reduction procedure and the set A is called an oracle. The reduction procedure is polynomial time-bounded if the algorithm runs in polynomial time when we stipulate that only one unit of time is to be charged for the execution of each subroutine call. Placing faith in our modified Church’s thesis and in Cobham’s thesis, these ideas, once again, are made precise via the oracle Turing machine.
Let M be an oracle Turing machine, let A be an oracle, and let T be a time-complexity function. We define an oracle Turing machine M with oracle A to be T(n) time-bounded if, for every input of length n, M makes at most T(n) moves before halting. If M is a nondeterministic oracle Turing machine, then every computation of M with A on words of length n must make at most T(n) moves before halting. The language accepted by M with oracle A is denoted L(M, A).
Let us consider once again the reduction procedure given in Fig. 3.2. For each input word x, the procedure makes a total of | x | queries to the oracle set B. This reduction procedure can be implemented on an oracle Turing machine that operates in time cn 2 for some constant c. Suppose the input word is 110. The string 110 is the first query to B. The second query to the oracle is either 1101 or 1100, depending on whether or not 110 belongs to B. There is a potential of 2 n different queries as B ranges over all possible oracles.
Definition 7.1.
A set A is Turing-reducible toBin polynomial-time (A ≤ PT B) if there exists a deterministic polynomial-time-bounded oracle Turing machine M such that A = L(M, B).
Download
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
Computer Vision & Pattern Recognition | Expert Systems |
Intelligence & Semantics | Machine Theory |
Natural Language Processing | Neural Networks |
Algorithms of the Intelligent Web by Haralambos Marmanis;Dmitry Babenko(8296)
Test-Driven Development with Java by Alan Mellor(6703)
Data Augmentation with Python by Duc Haba(6608)
Principles of Data Fabric by Sonia Mezzetta(6364)
Learn Blender Simulations the Right Way by Stephen Pearson(6257)
Microservices with Spring Boot 3 and Spring Cloud by Magnus Larsson(6125)
Hadoop in Practice by Alex Holmes(5958)
Jquery UI in Action : Master the concepts Of Jquery UI: A Step By Step Approach by ANMOL GOYAL(5806)
RPA Solution Architect's Handbook by Sachin Sahgal(5523)
Big Data Analysis with Python by Ivan Marin(5351)
The Infinite Retina by Robert Scoble Irena Cronin(5219)
Life 3.0: Being Human in the Age of Artificial Intelligence by Tegmark Max(5143)
Pretrain Vision and Large Language Models in Python by Emily Webber(4309)
Infrastructure as Code for Beginners by Russ McKendrick(4072)
Functional Programming in JavaScript by Mantyla Dan(4038)
The Age of Surveillance Capitalism by Shoshana Zuboff(3946)
WordPress Plugin Development Cookbook by Yannick Lefebvre(3786)
Embracing Microservices Design by Ovais Mehboob Ahmed Khan Nabil Siddiqui and Timothy Oleson(3588)
Applied Machine Learning for Healthcare and Life Sciences Using AWS by Ujjwal Ratan(3564)
