Feasible Computations and Provable Complexity Properties

Name: Feasible Computations and Provable Complexity Properties
Rating: 4 (2 reviews)

Juris Hartmanis

јан. 1978 г. · SIAM

4,0

2 рецензии

Е-книга

Страници

Соодветна

Оцените и рецензиите не се потврдени Дознајте повеќе

За е-книгава

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.

Оцени и рецензии

4,0

2 рецензии

Оценете ја е-книгава

Кажете ни што мислите.

Информации за читање

Паметни телефони и таблети

Инсталирајте ја апликацијата Google Play Books за Android и iPad/iPhone. Автоматски се синхронизира со сметката и ви овозможува да читате онлајн или офлајн каде и да сте.

Лаптопи и компјутери

Може да слушате аудиокниги купени од Google Play со користење на веб-прелистувачот на компјутерот.

Е-читачи и други уреди

За да читате на уреди со е-мастило, како што се е-читачите Kobo, ќе треба да преземете датотека и да ја префрлите на уредот. Следете ги деталните упатства во Центарот за помош за префрлање на датотеките на поддржани е-читачи.

Пријави незаконски содржини