On Tight Separation for Blum Measures Applied to Turing Machine Buffer Complexity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F17%3A00393220" target="_blank" >RIV/67985807:_____/17:00393220 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.3233/FI-2017-1526" target="_blank" >http://dx.doi.org/10.3233/FI-2017-1526</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/FI-2017-1526" target="_blank" >10.3233/FI-2017-1526</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Tight Separation for Blum Measures Applied to Turing Machine Buffer Complexity

Popis výsledku v původním jazyce

We formulate a very general tight diagonalization method for the Blum complexity measures satisfying two additional axioms related to our diagonalizer machine. We apply this method to two new, mutually related, distance and buffer complexities of Turing machine computations which are important nontrivial examples of natural Blum complexity measures different from time and space. In particular, these measures capture how many times the worktape head needs to move a certain distance during the computation which corresponds to the number of necessary block uploads into a buffer cache memory. We start this study by proving a tight separation which shows that a very small increase in the distance or buffer complexity bound (roughly from f(n) to f(n + 1)) brings provably more computational power to both deterministic and nondeterministic Turing machines even for unary languages. We also obtain hierarchies of the distance and buffer complexity classes.

Název v anglickém jazyce

On Tight Separation for Blum Measures Applied to Turing Machine Buffer Complexity

Popis výsledku anglicky

We formulate a very general tight diagonalization method for the Blum complexity measures satisfying two additional axioms related to our diagonalizer machine. We apply this method to two new, mutually related, distance and buffer complexities of Turing machine computations which are important nontrivial examples of natural Blum complexity measures different from time and space. In particular, these measures capture how many times the worktape head needs to move a certain distance during the computation which corresponds to the number of necessary block uploads into a buffer cache memory. We start this study by proving a tight separation which shows that a very small increase in the distance or buffer complexity bound (roughly from f(n) to f(n + 1)) brings provably more computational power to both deterministic and nondeterministic Turing machines even for unary languages. We also obtain hierarchies of the distance and buffer complexity classes.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Fundamenta Informaticae

ISSN

0169-2968

e-ISSN

—

Svazek periodika

152

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

397-409

Kód UT WoS článku

000401338000004

EID výsledku v databázi Scopus

2-s2.0-85019447188