Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Hartmanis J. — Feasible Computations and Provable Complexity Properties
Hartmanis J. — Feasible Computations and Provable Complexity Properties



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Feasible Computations and Provable Complexity Properties

Автор: Hartmanis J.

Аннотация:

An overview of current developments in research on feasible computations; and a consideration of this area of research in relation to provable properties of complexity of computations.

The author begins by defining and discussing efficient reductions between problems and considers the families and corresponding complete languages of NL, DCSL, CSL, P, NP, PTAPE, EXPTIME, and EXPTAPE. Definitions and results are uniformly extended to computationally simpler natural families of languages such as NL, P, and CSL by using Log n-tape bounded reductions.

The problem of determining what can and cannot be formally proven about running times of algorithms is discussed and related to the problem of establishing sharp time bounds for one-tape Turing machine computations, and the inability to formally prove running times for algorithms is then related to the presence of gaps in the hierarchy of complexity classes.

The concluding discussion is on the possibility that the famous P=NP? problem is independent of the axioms of formal mathematical systems such as set theory.



Язык: en

Статус предметного указателя: Неизвестно

ed2k: ed2k stats

Год издания: 1989

Количество страниц: 73

Добавлена в каталог: 25.04.2014

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте