Theory of Semi-Feasible Algorithms

Springer Science & Business Media
Free sample

An Invitation to the Dance It is an underappreciated fact that sets may have various types of complex ity, and not all types are in harmony with each other. The primary goal of this book is to unify and make more widely accessible a vibrant stream of research-the theory of semi-feasible computation-that perfectly showcases the richness of, and contrasts between, the central types of complexity. The semi-feasible sets, which are most commonly referred to as the P selective sets, are those sets L for which there is a deterministic polynornial time algorithm that, when given as input any two strings of which at least one belongs to L, will output one of them that is in L. The reason we saythat the semi-feasible sets showcase the contrasts among types of complexity is that it is well-known that many semi-feasible sets have no recursive algorithms (thus their time complexitycannot be upper-bounded by standard time-complexity classes), yet all semi-feasible sets are simple in a wide range of other natural senses. In particular, the semi-feasible sets have small circuits, they are in the extended low hierarchy, and they cannot be NP-complete unless P = NP. The semi-feasible sets are fascinating for many reasons. First, as men tioned above, they showcase the fact that mere deterministic time complex ity is not the only potential type of complexity in the world of computation.
Read more



Additional Information

Springer Science & Business Media
Read more
Published on
Apr 17, 2013
Read more
Read more
Read more
Read more
Best For
Read more
Read more
Computers / Data Processing
Computers / Information Technology
Computers / Machine Theory
Computers / Programming / Algorithms
Computers / Programming / General
Computers / User Interfaces
Mathematics / Combinatorics
Mathematics / Discrete Mathematics
Mathematics / Numerical Analysis
Read more
Content Protection
This content is DRM protected.
Read more

Reading information

Smartphones and Tablets

Install the Google Play Books app for Android and iPad/iPhone. It syncs automatically with your account and allows you to read online or offline wherever you are.

Laptops and Computers

You can read books purchased on Google Play using your computer's web browser.

eReaders and other devices

To read on e-ink devices like the Sony eReader or Barnes & Noble Nook, you'll need to download a file and transfer it to your device. Please follow the detailed Help center instructions to transfer the files to supported eReaders.
There's nothing that hard-core Unix and Linux users are more fanatical about than their text editor. Editors are the subject of adoration and worship, or of scorn and ridicule, depending upon whether the topic of discussion is your editor or someone else's.

vi has been the standard editor for close to 30 years. Popular on Unix and Linux, it has a growing following on Windows systems, too. Most experienced system administrators cite vi as their tool of choice. And since 1986, this book has been the guide for vi.

However, Unix systems are not what they were 30 years ago, and neither is this book. While retaining all the valuable features of previous editions, the 7th edition of Learning the vi and vim Editors has been expanded to include detailed information on vim, the leading vi clone. vim is the default version of vi on most Linux systems and on Mac OS X, and is available for many other operating systems too.

With this guide, you learn text editing basics and advanced tools for both editors, such as multi-window editing, how to write both interactive macros and scripts to extend the editor, and power tools for programmers -- all in the easy-to-follow style that has made this book a classic.

Learning the vi and vim Editors includes:

A complete introduction to text editing with vi:How to move around vi in a hurryBeyond the basics, such as using buffersvi's global search and replacementAdvanced editing, including customizing vi and executing Unix commands

How to make full use of vim:Extended text objects and more powerful regular expressionsMulti-window editing and powerful vim scriptsHow to make full use of the GUI version of vim, called gvimvim's enhancements for programmers, such as syntax highlighting, folding and extended tags

Coverage of three other popular vi clones -- nvi, elvis, and vile -- is also included. You'll find several valuable appendixes, including an alphabetical quick reference to both vi and ex mode commands for regular vi and for vim, plus an updated appendix on vi and the Internet.

Learning either vi or vim is required knowledge if you use Linux or Unix, and in either case, reading this book is essential. After reading this book, the choice of editor will be obvious for you too.
©2018 GoogleSite Terms of ServicePrivacyDevelopersArtistsAbout Google
By purchasing this item, you are transacting with Google Payments and agreeing to the Google Payments Terms of Service and Privacy Notice.