# Fundamentals of Computing

@article{Levin2020FundamentalsOC, title={Fundamentals of Computing}, author={Leonid A. Levin}, journal={ArXiv}, year={2020}, volume={abs/2005.06436} }

were systematically ignored. Concrete computational problems were considered only as illustrations of general principles. The notes (prepared by the students and revised by me) are skeletal: they do have (terse) proofs, but exercises, references, intuitive comments and examples are missing or inadequate. The better is English in a paragraph the smaller was my contribution and the greater caution is needed. The notes can be used by an instructor designing a course or by students who either know… Expand

#### Topics from this paper

#### One Citation

Searching of all Occurences of a Word in a String

This paper presents a string search algorithm. The method searches to find all occurences of a word p of m characters in a string s of n characters, 0<m≤ n. The upper bound of the number of… Expand

#### References

SHOWING 1-10 OF 167 REFERENCES

An Introduction to Kolmogorov Complexity and Its Applications

- Computer Science, Psychology
- Texts and Monographs in Computer Science
- 1993

The book presents a thorough treatment of the central ideas and their applications of Kolmogorov complexity with a wide range of illustrative applications, and will be ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics. Expand

A Machine-Independent Theory of the Complexity of Recursive Functions

- Computer Science
- JACM
- 1967

The number of steps required to compute a function depends on the type of computer that is used, on the choice of computer program, and on the input-output code, but the results obtained in this paper are nearly independent of these considerations. Expand

Average-case Complexity

- Computer Science
- 2008 49th Annual IEEE Symposium on Foundations of Computer Science
- 2008

The many open questions and the few things that are known about the average-case complexity of computational problems are reviewed, and a theory of completeness for distributional problems under reductions that preserveaverage-case tractability is initiated. Expand

Algorithms and Complexity

- Mathematics, Computer Science
- Lecture Notes in Computer Science
- 1997

A computation that is guaranteed to take at most cn3 time for input of size n will be thought of as an ‘easy’ computation, and one that needs at most n10 time is also easy. Expand

A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms

- Computer Science
- Annals of the History of Computing
- 1984

This paper is a personal account of some events, ideas, and academic controversies that surrounded the discovery and investigation of non-deterministic polynomial (NP)-complete problems independently by S. Cook and R. Karp in the United States and L. Levin in the Soviet Union. Expand

The NP-completeness column

- Mathematics, Computer Science
- TALG
- 2005

This is the 24th edition of a column that covers new developments in the theory of NP-completeness and the history and purpose of the column and the status of the open problems from [G&J] and previous columns. Expand

An Introduction To Probability Theory And Its Applications

- Computer Science
- 1950

A First Course in Probability (8th ed.) by S. Ross is a lively text that covers the basic ideas of probability theory including those needed in statistics. Expand

Storage Modification Machines

- Computer Science
- SIAM J. Comput.
- 1980

This paper gives a complete description of the SMM model and its real time equivalence to the so-called successor RAMS and shows the existence of an SMM that performs integer-multiplication in linear time. Expand

N by N Checkers is Exptime Complete

- Mathematics, Computer Science
- SIAM J. Comput.
- 1984

The question of whether a particular player can force a win from a given position and also the question of what is the best move in agiven position are considered. Expand

Theory of Recursive Functions and Effective Computability

- Computer Science
- 1969

If searching for the ebook by Hartley Rogers Theory of Recursive Functions and Effective Computability in pdf format, then you've come to the faithful site. We presented the complete version of this… Expand