Feasible Computations and Provable Complexity Properties
Juris Hartmanis
jan 1978. · CBMS-NSF Regional Conference Series in Applied Mathematics 30. knjiga · SIAM
4,0star
2 recenzijereport
E-knjiga
69
Broj stranica
family_home
Prihvatljiva
info
reportOcjene i recenzije nisu potvrđene Saznajte više
O ovoj e-knjizi
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.
Ocjene i recenzije
4,0
2 recenzije
Ocijenite ovu e-knjigu
Recite nam šta mislite.
Informacije o čitanju
Pametni telefoni i tableti
Instalirajte aplikaciju Google Play Knjige za Android i iPad/iPhone uređaje. Aplikacija se automatski sinhronizira s vašim računom i omogućava vam čitanje na mreži ili van nje gdje god da se nalazite.
Laptopi i računari
Audio knjige koje su kupljene na Google Playu možete slušati pomoću web preglednika na vašem računaru.
Elektronički čitači i ostali uređaji
Da čitate na e-ink uređajima kao što su Kobo e-čitači, morat ćete preuzeti fajl i prenijeti ga na uređaj. Pratite detaljne upute Centra za pomoć da prenesete fajlove na podržane e-čitače.
