|
|
libcats.org
Главная →
Feasible Computations and Provable Complexity Properties (CBMS-NSF Regional Conference Series in Applied Mathematics)Feasible Computations and Provable Complexity Properties (CBMS-NSF Regional Conference Series in Applied Mathematics)Juris HartmanisAn 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.
Скачать книгу бесплатно (pdf, 4.61 Mb)
Читать «Feasible Computations and Provable Complexity Properties (CBMS-NSF Regional Conference Series in Applied Mathematics)» EPUB | FB2 | MOBI | TXT | RTF
* Конвертация файла может нарушить форматирование оригинала. По-возможности скачивайте файл в оригинальном формате.
Популярные книги за неделю:
Проектирование и строительство. Дом, квартира, садАвтор: Петер Нойферт, Автор: Людвиг Нефф
Размер книги: 20.83 Mb
Система упражнений по развитию способностей человека (Практическое пособие)Автор: Петров Аркадий НаумовичКатегория: Путь к себе
Размер книги: 818 Kb
Сотворение мира (3-х томник)Автор: Петров Аркадий НаумовичКатегория: Путь к себе
Размер книги: 817 Kb
Радиолюбительские схемы на ИС типа 555Автор: Трейстер Р.Категория: Электротехника и связь
Размер книги: 13.64 Mb
Только что пользователи скачали эти книги:
Show Sold Separately: Promos, Spoilers, and Other Media ParatextsАвтор: Jonathan Gray
Размер книги: 2.54 Mb
Programming 32-bit Microcontrollers in C: Exploring the PIC32 (Embedded Technology)Автор: Lucio Di JasioКатегория: Компьютеры, Программирование
Размер книги: 5.18 Mb
Жизнь - движение воды в организмеАвтор: Барабанов В.И. , Автор: Горшков А.С. , Автор: Сабатович В.Е.Категория: КНИГИ ЗДОРОВЬЕ
Размер книги: 2.65 Mb
Radiation Effects in Advanced Semiconductor Materials and Devices (Springer Series in Materials Science)Автор: C. Claeys, Автор: E. Simoen
Размер книги: 5.36 Mb
|
|
|